A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Descriptional Complexity of Unambiguous Nested Word Automata
Tekijät: Okhotin A, Salomaa K
Julkaisuvuosi: 2011
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Language and Automata Theory and Applications (LATA 2011)
Tietokannassa oleva lehden nimi: LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 6638
Aloitussivu: 414
Lopetussivu: 426
Sivujen määrä: 13
ISBN: 978-3-642-21253-6
ISSN: 0302-9743
Tiivistelmä
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)).
Turun yliopiston Tutkimustietojärjestelmän portaali