Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Converting Two—Way Nondeterministic Unary Automata into Simpler Automata
| |
|
Converting Two—Way Nondeterministic Unary Automata into Simpler Automata
Viliam Geffert6  , Carlo Mereghetti7 and Giovanni Pighizzini8
| (6) |
Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia |
| (7) |
Dipartimento di Inf., Sist. e Com., Università degli Studi di Milano, Bicocca via Bicocca degli Arcimboldi 8, 20126 Milano, Italy |
| (8) |
Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy |
Abstract
We show that, on inputs of length exceeding 5n
2, any n-state unary 2nfa (two-way nondeterministic finite automaton) can be simulated by a (2n+2)-state quasi sweeping 2nfa. Such a result, besides providing a “normal form” for 2nfa’s, enables us to get a subexponential
simulation of unary 2nfa’s by 2dfa’s (two-way deterministic finite automata). In fact, we prove that any n-state unary 2nfa can be simulated by a 2dfa with O(n
logn+4) states.
Keywords formal languages - finite state automata - unary languages
Supported by the Slovak Grant Agency for Science (VEGA) under contract #1/7465/20 “Combinatorial Structures and Complexity
of Algorithms.”
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|