Answers are grounded in this paper and cite their sources.
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 with F(n)=max_(k+l=n, m <= l) k (l m) (k - 1 l - m) (l - m)! states. This number of states is proved to be necessary in the worst case, and its growth rate is estimated as F(n) = n^(n/2 - (1 + ln 2)/2 · n/(ln n) · (1 + o(1))).
No takes yet. Share an insight, caveat, or question.
Radionova et al. (2023) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: