The family of deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ("Visibly pushdown languages", STOC 2004), the reversal and the Kleene star of an n-state IDPDA can be represented by an IDPDA 2O(n2) with states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2O((m+n)2) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ(n log n) states, as well as an m 2 Θ(n log n)-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings
Pages485-496
Number of pages12
DOIs
StatePublished - 2011
Externally publishedYes
Event36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011 - Warsaw, Poland
Duration: 22 Aug 201126 Aug 2011

Publication series

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

Conference

Conference36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011
Country/TerritoryPoland
CityWarsaw
Period22/08/1126/08/11

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78945375