TY - GEN
T1 - Input-driven pushdown automata with limited nondeterminism (Invited Paper)
AU - Okhotin, Alexander
AU - Salomaa, Kai
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84958546855&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09698-8_9
DO - 10.1007/978-3-319-09698-8_9
M3 - Conference contribution
AN - SCOPUS:84958546855
SN - 9783319096971
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 84
EP - 102
BT - Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings
PB - Springer Nature
T2 - 18th International Conference on Developments in Language Theory, DLT 2014
Y2 - 26 August 2014 through 29 August 2014
ER -