The AC0-complexity of visibly pushdown languages.

Prelegent(ci)

Stefan Göller

Afiliacja

Universität Kassel

Termin

11 października 2022 14:15

Pokój

p. 5820

Seminarium

Seminarium „Teoria automatów”

---

The talk will be on the question which visibly pushdown languages (VPLs) are in the complexity class AC0. We provide a conjectural characterization that isolates a stubborn subclass of very particular one-turn visibly pushdown languages (that we call intermediate VPLs) any of which our community seems to lack tools for determining containment in AC0. Our first main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs if its language is in AC0, not in AC0, or constant-depth equivalent to a finite disjoint union of such intermediate languages. Our second main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs if its language is in AC0, hard for MOD_m for some m>1, or hard for some more concrete intermediate language generated the context free grammar S-> epsilon | ab^iSc | ab^jSd for some distinct i and j. For our proofs we revisit so-called Ext-algebras, introduced by Czarnetzki, Krebs and Lange, which in turn are closely related to forest algebras introduced by Bojańczyk and Walukiewicz. The talk will be based on joint work with Nathan Grosshans.

---