Input-driven pushdown automata with limited nondeterminism (Invited Paper)

Alexander Okhotin, Kai Salomaa

Research output

2 Citations (Scopus)

Abstract

It is known that determinizing a nondeterministic input-driven pushdown automaton (NIDPDA) of size n results in the worst case in a machine of size (R. Alur, P. Madhusudan, "Adding nesting structure to words", J.ACM 56(3), 2009). This paper considers the special case of k-path NIDPDAs, which have at most k computations on any input. It is shown that the smallest deterministic IDPDA equivalent to a k-path NIDPDA of size n is of size Θ(n k ). The paper also gives an algorithm for deciding whether or not a given NIDPDA has the k-path property, for a given k; if k is fixed, the problem is P-complete.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 18th International Conference, DLT 2014, Proceedings
PublisherSpringer Nature
Pages84-102
Number of pages19
ISBN (Print)9783319096971
DOIs
Publication statusPublished - 1 Jan 2014
Event18th International Conference on Developments in Language Theory, DLT 2014 - Ekaterinburg
Duration: 26 Aug 201429 Aug 2014

Publication series

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

Conference

Conference18th International Conference on Developments in Language Theory, DLT 2014
CountryRussian Federation
CityEkaterinburg
Period26/08/1429/08/14

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Input-driven pushdown automata with limited nondeterminism (Invited Paper)'. Together they form a unique fingerprint.

Cite this