Scholarlink

<p>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”, <i>Mathematical Systems Theory</i>, 1968). The proof is constructive: an <i>n</i>-state two-way permutation automaton is transformed to a one-way permutation automaton with at most <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(F(n)=\max _{k+\ell =n, m \leqslant \ell } k \cdot { \ell \atopwithdelims ()m} \cdot {k - 1 \atopwithdelims ()\ell - m} \cdot (\ell - m)!\)</EquationSource> </InlineEquation> states (here the maximum is over all partitions of <i>n</i> into <i>k</i> states with transitions to the right and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\ell\)</EquationSource> </InlineEquation> states with transitions to the left, where <i>m</i> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(F(n) = n^{\frac{n}{2} - \frac{1 + \ln 2}{2}\frac{n}{\ln n}(1 + o(1))}\)</EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Sweeping permutation automata

  • 期刊论文

  • 发表日期：

    2026年1月31日

查看全文
  • Maria Radionova,
  • Alexander Okhotin

摘要

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 \(F(n)=\max _{k+\ell =n, m \leqslant \ell } k \cdot { \ell \atopwithdelims ()m} \cdot {k - 1 \atopwithdelims ()\ell - m} \cdot (\ell - m)!\) states (here the maximum is over all partitions of n into k states with transitions to the right and \(\ell\) 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 \(F(n) = n^{\frac{n}{2} - \frac{1 + \ln 2}{2}\frac{n}{\ln n}(1 + o(1))}\) .