A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
State complexity of operations on input-driven pushdown automata
Tekijät: Alexander Okhotin, Kai Salomaa
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2017
Journal: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Vuosikerta: 86
Aloitussivu: 207
Lopetussivu: 228
Sivujen määrä: 22
ISSN: 0022-0000
eISSN: 1090-2724
DOI: https://doi.org/10.1016/j.jcss.2017.02.001
Tiivistelmä
The family of languages recognized by deterministic input -driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) [2], the Kleene star and the reversal 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 Kleene star and for the reversal, 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 up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) [27]. (C) 2017 Elsevier Inc. All rights reserved.
The family of languages recognized by deterministic input -driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) [2], the Kleene star and the reversal 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 Kleene star and for the reversal, 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 up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) [27]. (C) 2017 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali