Superdeterministic DPDAs: The method of accepting does affect decision problems

摘要

A deterministic pushdown store automaton is superdeterministic if it is finite delay and whenever two configurations c1 and c′1 in the same state and in reading mode are taken by the same input into two configurations c2 and c′2 in reading mode, then c2 and c2 are also in the same state and the change in stack height between c1 and c2 is the same as that between c′1 and c′2 . Although it is decidable whether an arbitrary context-free language is included in the language accepted by a superdeterministic pushdown store automaton by final state and empty store, inclusion is undecidable for languages accepted by final state or accept mode by superdeterministic pushdown store automata. Equivalence is decidable for superdeterministic pushdown store automata (for either method of acceptance) in time O(2p(n)), p a polynomial.