Removing Nondeterminism in Constant Height Pushdown Automata

摘要

We study the descriptional cost of converting constant height nondeterministic pushdown automata into equivalent deterministic devices. We show a double-exponential upper bound for this conversion, together with a super-exponential lower bound.