TY - JOUR

T1 - On the transformation of two-way finite automata to unambiguous finite automata

AU - Петров, Семен Андреевич

AU - Охотин, Александр Сергеевич

PY - 2023/12/1

Y1 - 2023/12/1

N2 - This paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA) and an n-state two-way unambiguous finite automaton (2UFA). It is proved that a 2UFA with n states can be transformed to a UFA with fewer than 2n⋅n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((2+1)2n⋅n−1)=Ω(5.828n) states. The latter result is obtained as a lower bound on the rank of a certain matrix.

AB - This paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n-state two-way deterministic finite automaton (2DFA) and an n-state two-way unambiguous finite automaton (2UFA). It is proved that a 2UFA with n states can be transformed to a UFA with fewer than 2n⋅n! states. On the other hand, for every n, there is a language recognized by an n-state 2DFA that requires a UFA with at least Ω((2+1)2n⋅n−1)=Ω(5.828n) states. The latter result is obtained as a lower bound on the rank of a certain matrix.

KW - Descriptional complexity

KW - Two-way finite automata

KW - Unambiguous finite automata

UR - https://www.mendeley.com/catalogue/4a382b13-568b-3f5b-933b-a285f3f844c7/

U2 - 10.1016/j.ic.2022.104956

DO - 10.1016/j.ic.2022.104956

M3 - Conference article

VL - 295

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - A

M1 - 104956

T2 - 15th International Conference on Language and Automata Theory and Applications, LATA 2021

Y2 - 1 March 2021 through 5 March 2021

ER -