TY - JOUR

T1 - Sweeping permutation automata

AU - Radionova, M

AU - Okhotin, A

N1 - Times Cited in Web of Science Core Collection: 0 Total Times Cited: 0

PY - 2026/1/31

Y1 - 2026/1/31

N2 - This paper introduces sweeping permutation automata, which move over an input string in alternating left-to-right and right-to-left sweeps and have a bijective transition function. It is proved that these automata recognize the same family of languages as the classical one-way permutation automata (Thierrin, "Permutation automata", Mathematical Systems Theory, 1968). The proof is constructive: an n-state two-way permutation automaton is transformed to a one-way permutation automaton with at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(n)=\max _{k+\ell =n, m \leqslant \ell } k \cdot { \ell \atopwithdelims ()m} \cdot {k - 1 \atopwithdelims ()\ell - m} \cdot (\ell - m)!$$\end{document} states (here the maximum is over all partitions of n into k states with transitions to the right and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} states with transitions to the left, where m states have no transitions on the left end-marker). This number of states is proved to be necessary in the worst case, and its growth rate is estimated as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(n) = n{\frac{n}{2} - \frac{1 + \ln 2}{2}\frac{n}{\ln n}(1 + o(1))}$$\end{document}.

AB - This paper introduces sweeping permutation automata, which move over an input string in alternating left-to-right and right-to-left sweeps and have a bijective transition function. It is proved that these automata recognize the same family of languages as the classical one-way permutation automata (Thierrin, "Permutation automata", Mathematical Systems Theory, 1968). The proof is constructive: an n-state two-way permutation automaton is transformed to a one-way permutation automaton with at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(n)=\max _{k+\ell =n, m \leqslant \ell } k \cdot { \ell \atopwithdelims ()m} \cdot {k - 1 \atopwithdelims ()\ell - m} \cdot (\ell - m)!$$\end{document} states (here the maximum is over all partitions of n into k states with transitions to the right and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} states with transitions to the left, where m states have no transitions on the left end-marker). This number of states is proved to be necessary in the worst case, and its growth rate is estimated as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(n) = n{\frac{n}{2} - \frac{1 + \ln 2}{2}\frac{n}{\ln n}(1 + o(1))}$$\end{document}.

KW - STATE COMPLEXITY

KW - OPERATIONS

U2 - 10.1007/s00236-025-00519-6

DO - 10.1007/s00236-025-00519-6

M3 - статья

VL - 63

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

IS - 1

ER -