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 -