Descriptional complexity of unambiguous nested word automata

Alexander Okhotin, Kai Salomaa

Research output

5 Citations (Scopus)

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 Θ(n2) states (R. Alur, P. Madhusudan: Adding nesting structure to words, DLT'06). We show that the same worst case 2Θ(n2) size blow-up 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).

Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications - 5th International Conference, LATA 2011, Proceedings
Pages414-426
Number of pages13
DOIs
Publication statusPublished - 8 Jun 2011
Event5th International Conference on Language and Automata Theory and Applications, LATA2011 - Tarragona
Duration: 26 May 201131 May 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6638 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Language and Automata Theory and Applications, LATA2011
CountrySpain
CityTarragona
Period26/05/1131/05/11

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Descriptional complexity of unambiguous nested word automata'. Together they form a unique fingerprint.

Cite this