← All problems
Unverified

Succinctness of GFG pushdown automata

Valiant showed that the succinctness gap between deterministic and nondeterministic pushdown automata (restricted to deterministic contextfree languages) is nonrecursive, i.e., there is no computable function ff with the following property: If the language of a pushdown automaton AA is deterministic contextfree, then there is a deterministic pushdown automaton of size f(∣A∣)f(|A|) recognizing L(A)L(A). Recently, good-for-games pushdown automata have been introduced, whose expressive power is strictly between the deterministic contextfree and the contextfree languages. This new class of automata opens new succinctness gaps, i.e., between deterministic pushdown automata and good-for-games pushdown automata (restricted to deterministic contextfree languages), between good-for-games pushdown automata and pushdown automata (restricted to deterministic contextfree languages), and between good-for-games pushdown automata and pushdown automata (restricted to good-for-games contextfree languages). The extent of these new gaps is open, but Valiant's result implies that at least one of the first two gaps has to be nonrecursive.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu