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Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure towords, DLT'06).We show that the same worst case 2Θ(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Θ(n2), and that the state complexity of homomorphism for deterministic nested word automata is 2Θ(n2).
['Alexander Okhotin', 'Kai Salomaa']
Descriptional complexity of unambiguous nested word automata