A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
State Complexity of Operations on Input-Driven Pushdown Automata
Tekijät: Okhotin A, Salomaa K
Julkaisuvuosi: 2011
Journal: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2011
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 6907
Aloitussivu: 485
Lopetussivu: 496
Sivujen määrä: 12
ISBN: 978-3-642-22992-3
ISSN: 0302-9743
Tiivistelmä
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 with 2(O(n2)) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2(O((m+n)2)) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2(Theta(n log n)) states, as well as an m2(Theta(n log n))-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.
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 with 2(O(n2)) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2(O((m+n)2)) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2(Theta(n log n)) states, as well as an m2(Theta(n log n))-state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.
Turun yliopiston Tutkimustietojärjestelmän portaali