TY - GEN

T1 - Transforming two-way alternating finite automata to one-way nondeterministic automata

AU - Geffert, Viliam

AU - Okhotin, Alexander

PY - 2014/1/1

Y1 - 2014/1/1

N2 - It is proved that a two-way alternating finite automaton (2AFA) with n states can be transformed to an equivalent one-way nondeterministic finite automaton (1NFA) with f(n)=2Θ(n logn) states, and that this number of states is necessary in the worst case already for the transformation of a two-way automaton with universal nondeterminism (2Π1FA) to a 1NFA. At the same time, an n-state 2AFA is transformed to a 1NFA with (2 n -1)2+1 states recognizing the complement of the original language, and this number of states is again necessary in the worst case. The difference between these two trade-offs is used to show that complementing a 2AFA requires at least Ω(n logn) states.

AB - It is proved that a two-way alternating finite automaton (2AFA) with n states can be transformed to an equivalent one-way nondeterministic finite automaton (1NFA) with f(n)=2Θ(n logn) states, and that this number of states is necessary in the worst case already for the transformation of a two-way automaton with universal nondeterminism (2Π1FA) to a 1NFA. At the same time, an n-state 2AFA is transformed to a 1NFA with (2 n -1)2+1 states recognizing the complement of the original language, and this number of states is again necessary in the worst case. The difference between these two trade-offs is used to show that complementing a 2AFA requires at least Ω(n logn) states.

UR - http://www.scopus.com/inward/record.url?scp=84958528853&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-44522-8_25

DO - 10.1007/978-3-662-44522-8_25

M3 - Conference contribution

AN - SCOPUS:84958528853

SN - 9783662445211

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 291

EP - 302

BT - Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings

PB - Springer Nature

T2 - 39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014

Y2 - 25 August 2014 through 29 August 2014

ER -