Sweeping Permutation Automata
Maria S. Radionova, Alexander Okhotin · Electronic Proceedings in Theoretical Computer Science · 2023
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).An n-state two-way permutation automaton is transformed to a one-way permutation automaton withThis number of states is proved to be necessary in the worst case, and its growth rate is estimated as )) .