Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata

Galina Jirásková, Alexander Okhotin

Research outputpeer-review

1 Citation (Scopus)

Abstract

The paper improves several state complexity bounds for input-driven pushdown automata (IDPDA), also known as visibly pushdown automata. For deterministic IDPDA it is proved that the number of states sufficient and in the worst case necessary to represent the reversal of an n-state automaton is exactly if all inputs are assumed to be well-nested, and between and (formula presented) without this restriction, cf. (formula presented) in the literature. For the concatenation of an m-state and an n-state IDPDA, the new lower bound is which is asymptotically tight for well-nested inputs. Without this restriction, the state complexity is between and Finally, it is proved that transforming an n-state nondeterministic IDPDA to a deterministic one requires exactly states, cf. in the literature; the known lower bounds on complementing nondeterministic IDPDA and on transforming them to unambiguous are also improved.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 22nd International Conference, DLT 2018, Proceedings
EditorsMizuho Hoshi, Shinnosuke Seki
PublisherSpringer Nature
Pages441-452
Number of pages12
ISBN (Print)9783319986531
DOIs
Publication statusPublished - 1 Jan 2018
Event22nd International Conference on Developments in Language Theory, DLT 2018 - Tokyo
Duration: 10 Sep 201814 Sep 2018

Publication series

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

Conference

Conference22nd International Conference on Developments in Language Theory, DLT 2018
CountryJapan
CityTokyo
Period10/09/1814/09/18

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata'. Together they form a unique fingerprint.

  • Cite this

    Jirásková, G., & Okhotin, A. (2018). Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata. In M. Hoshi, & S. Seki (Eds.), Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings (pp. 441-452). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11088 LNCS). Springer Nature. https://doi.org/10.1007/978-3-319-98654-8_36