A4 Refereed article in a conference publication
Descriptional Complexity of Unambiguous Nested Word Automata
Authors: Okhotin A, Salomaa K
Publication year: 2011
Journal: Lecture Notes in Computer Science
Book title : Language and Automata Theory and Applications (LATA 2011)
Journal name in source: LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
Journal acronym: LECT NOTES COMPUT SC
Volume: 6638
First page : 414
Last page: 426
Number of pages: 13
ISBN: 978-3-642-21253-6
ISSN: 0302-9743
Abstract
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)).
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)).
UTU Research Portal