A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Descriptional complexity of unambiguous input-driven pushdown automata




TekijätAlexander Okhotin, Kai Salomaa

KustantajaELSEVIER SCIENCE BV

Julkaisuvuosi2015

JournalTheoretical Computer Science

Tietokannassa oleva lehden nimiTHEORETICAL COMPUTER SCIENCE

Lehden akronyymiTHEOR COMPUT SCI

Vuosikerta566

Aloitussivu1

Lopetussivu11

Sivujen määrä11

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2014.11.015


Tiivistelmä

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a. visibly pushdown automaton; a.k.a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2(Theta(n2)) states (B. von Braunmuhl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2(Theta(n2)) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2(Theta(n2)), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2(Theta(n2)).




Last updated on 2024-26-11 at 15:44