Back to Search
Start Over
Deciding path size of nondeterministic (and input-driven) pushdown automata.
- Source :
-
Theoretical Computer Science . Jan2023, Vol. 939, p170-181. 12p. - Publication Year :
- 2023
-
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). • We show that finiteness of path size of nondeterministic pushdown automata can be solved in polynomial time. • We show that deciding k-path property is PSPACE complete for nondeterministic finite automata. • We show that deciding k-path property is exponential time complete for nondeterministic input-driven pushdown automata. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 939
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 160210337
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.10.023