2023/02/25 by Stefan Göller, Göller, Stefan, Nathan Grosshans +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Machine Learning and Algorithms #cs.CC #cs.FL #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2302.13116
openalex publication_date 2023/02/25 · openalex created_date 2023/03/03 · openalex updated_date 2026/07/28 · arxiv created 2026/08/05 · arxiv updated 2026/08/06
We study the question of which visibly pushdown languages (VPLs) are in the complexity class AC0 and how to effectively decide this question. Our contribution is to introduce a particular subclass of one-turn VPLs, called intermediate VPLs, for which the raised question is entirely unclear: to the best of our knowledge our research community is unaware of containment or non-containment in AC0 for any language in our newly introduced class. Our main result states that there is an algorithm that, given a visibly pushdown automaton, correctly outputs exactly one of the following: that its language L is in AC0, some m≥ 2 such that L is ACC0(m)-hard (implying that L is not in AC0), or a finite disjoint union of intermediate VPLs that L is constant-depth equivalent to. In the latter of the three cases one can moreover effectively compute k,l∈ℕ>0 with k\not=l such that the concrete intermediate VPL L(S→ ε| a ck-1 S b1| acl-1Sb2) is constant-depth reducible to the language L. Due to their particular nature we conjecture that either all intermediate VPLs are in AC0 or all are not. As a corollary of our main result we obtain that in case the input language is a visibly counter language our algorithm can effectively determine if it is in AC0 - hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in AC0 (when restricted to well-matched words). For our proofs we revisit so-called Ext-algebras (introduced by Czarnetzki et al.), which are closely related to forest algebras (introduced by BojaÅ„czyk and Walukiewicz), and use Green's relations.