Deciding path size of nondeterministic (and input-driven) pushdown automata

Yo Sub Han, Sang Ki Ko, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The degree of ambiguity (respectively, the path size) of a nondeterministic automaton, on a given input, measures the number of accepting computations (respectively, the number of all computations). It is known that deciding the finiteness of the degree of ambiguity of a nondeterministic pushdown automaton is undecidable. Also, it is undecidable for a given k≥3 to decide whether the path size of a nondeterministic pushdown automaton is bounded by k. As the main result, we show that deciding the finiteness of the path size of a nondeterministic pushdown automaton can be done in polynomial time. Also, we show that the k-path problem for nondeterministic input-driven pushdown automata (respectively, for nondeterministic finite automata) is complete for exponential time (respectively, complete for polynomial space).

Original languageEnglish
Pages (from-to)170-181
Number of pages12
JournalTheoretical Computer Science
Volume939
DOIs
StatePublished - 4 Jan 2023

Keywords

  • Ambiguity
  • Decidability
  • Input-driven pushdown automaton
  • Measures of nondeterminism
  • Path size

Fingerprint

Dive into the research topics of 'Deciding path size of nondeterministic (and input-driven) pushdown automata'. Together they form a unique fingerprint.

Cite this