Input-Driven Pushdown Automata with Limited Nondeterminism (Invited Paper)
Alexander Okhotin, Kai Salomaa · Developments in Language Theory · 2014
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 2 Θ(n 2 ) (R. Alur, P. Madhusudan, Adding nest- ing 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 ;i fk is fixed, the problem is P-complete.