Descriptional Complexity of Unambiguous Nested Word Automata

: Okhotin A, Salomaa K

: 2011

: Lecture Notes in Computer Science

: Language and Automata Theory and Applications (LATA 2011)

: LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS

: LECT NOTES COMPUT SC

: 6638

: 414

: 426

: 13

: 978-3-642-21253-6

: 0302-9743

It is known that converting an n-state nondeterministic nested word automaton (a.k.a. input-driven automaton; a.k.a. visibly pushdown automaton) to a corresponding deterministic automaton requires in the worst case 2(circle minus(n2)) states (R. Alur; P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2(circle minus(n2)) size blowup occurs when converting a nondeterministic nested word automaton to an unambiguous one, and an unambiguous nested word automaton to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the state complexity of complementation for nondeterministic nested word automata is 2(circle minus(n2)); and that the state complexity of homomorphism for deterministic nested word automata is 2(circle minus(n2)).