@article{HAN2022,
    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).},
    Author = {Han, Yo-Sub and Ko, Sang-Ki and Salomaa, Kai},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {measures of nondeterminism, path size, ambiguity, input-driven pushdown automaton, decidability},
    Title = {Deciding Path Size of Nondeterministic (and Input-Driven) Pushdown Automata},
    URL = {https://www.sciencedirect.com/science/article/pii/S0304397522006193},
    Year = {2022},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397522006193},
    bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2022.10.023},
    date-added = {2022-11-04 09:22:29 +0100},
    date-modified = {2022-11-04 09:22:29 +0100},
    doi = {10.1016/j.tcs.2022.10.023}
}

@article{HAN2022, 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).}, Author = {Han, Yo-Sub and Ko, Sang-Ki and Salomaa, Kai}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {measures of nondeterminism, path size, ambiguity, input-driven pushdown automaton, decidability}, Title = {Deciding Path Size of Nondeterministic (and Input-Driven) Pushdown Automata}, URL = {https://www.sciencedirect.com/science/article/pii/S0304397522006193}, Year = {2022}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0304397522006193}, bdsk-url-2 = {https://doi.org/10.1016/j.tcs.2022.10.023}, date-added = {2022-11-04 09:22:29 +0100}, date-modified = {2022-11-04 09:22:29 +0100}, doi = {10.1016/j.tcs.2022.10.023} }