pith. sign in

arxiv: 2302.13116 · v4 · submitted 2023-02-25 · 💻 cs.FL · cs.CC· cs.LO

The mathsf{AC}⁰-Complexity Of Visibly Pushdown Languages

Stefan G\"oller , Nathan Grosshans This is my paper

Pith reviewed 2026-05-24 10:09 UTC · model grok-4.3

classification 💻 cs.FL cs.CCcs.LO
keywords visibly pushdown languagesAC^0ACC^0intermediate VPLsExt-algebrasGreen's relationsconstant-depth reductionsvisibly counter languages
0
0 comments X

The pith

There is an algorithm that, given any visibly pushdown automaton, outputs either that its language lies in AC^0, that it is hard for ACC^0(m) for some m at least 2, or a constant-depth equivalence to a finite union of intermediate VPLs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines which visibly pushdown languages belong to the circuit class AC^0 and supplies an effective procedure to resolve the question for every input language. It defines a new subclass of one-turn visibly pushdown languages called intermediate VPLs whose membership in AC^0 remains open. The central algorithm takes a visibly pushdown automaton and returns one of three outputs: confirmation that the language is in AC^0, a hardness proof for ACC^0 with a concrete modulus, or an explicit reduction of the language to a finite disjoint union of intermediate VPLs together with concrete parameters k and l showing a specific generator language reduces to it. The same procedure decides the AC^0 question completely when the input is restricted to visibly counter languages.

Core claim

There is an algorithm that, given a visibly pushdown automaton, correctly outputs either that its language is in AC^0, outputs some m≥2 such that L is ACC^0(m)-hard (implying that L is not in AC^0), or outputs a finite disjoint union of intermediate VPLs that L is constant-depth equivalent to. In the latter case one can moreover effectively compute k,l∈N>0 with k≠l such that the concrete intermediate VPL L(S→ε | a c^{k-1} S b1 | a c^{l-1} S b2) is constant-depth reducible to the language L.

What carries the argument

Ext-algebras equipped with Green's relations, which classify the possible constant-depth behaviors of visibly pushdown automata into the three output categories.

If this is right

  • Membership in AC^0 becomes decidable for every visibly counter language.
  • If the status of any single intermediate VPL with respect to AC^0 is settled, the same status holds for all of them under the authors' conjecture.
  • Constant-depth reducibility between a given language and a concrete generator intermediate VPL can be computed explicitly when the third case applies.
  • The AC^0 question for the full class of visibly pushdown languages reduces to the single open question about intermediate VPLs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Resolving the conjecture that all intermediate VPLs lie on the same side of AC^0 would yield a complete decision procedure for every visibly pushdown language.
  • The reduction technique may extend to deciding other low-depth circuit properties for languages recognized by pushdown automata.
  • The concrete generator intermediate VPLs with parameters k and l could serve as canonical hard instances for proving new constant-depth lower bounds.

Load-bearing premise

The algebraic properties of Ext-algebras and Green's relations are enough to place every visibly pushdown language into exactly one of the three categories without gaps.

What would settle it

A visibly pushdown automaton whose language the procedure cannot assign to AC^0 membership, ACC^0(m) hardness, or constant-depth equivalence to any finite union of intermediate VPLs.

read the original abstract

We study the question of which visibly pushdown languages (VPLs) are in the complexity class $\mathsf{AC}^0$ 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 $\mathsf{AC}^0$ 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 either that its language is in $\mathsf{AC}^0$, outputs some $m\geq 2$ such that $L$ is $\mathsf{ACC}^0(m)$-hard (implying that $L$ is not in $\mathsf{AC}^0$), or outputs a finite disjoint union of intermediate VPLs that $L$ is constant-depth equivalent to. In the latter case one can moreover effectively compute $k,l\in\mathbb{N}_{>0}$ with $k\not=l$ such that the concrete intermediate VPL $L(S\rightarrow\varepsilon\mid a c^{k-1} S b_1\mid ac^{l-1}Sb_2)$ is constant-depth reducible to the language $L$. Due to their particular nature we conjecture that either all intermediate VPLs are in $\mathsf{AC}^0$ 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 $\mathsf{AC}^0$ - hence our main result generalizes a result by Krebs et al. stating that it is decidable if a given visibly counter language is in $\mathsf{AC}^0$ (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\'nczyk and Walukiewicz), and use Green's relations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper introduces a subclass of one-turn visibly pushdown languages called intermediate VPLs and claims an algorithm that, given any visibly pushdown automaton, outputs one of three possibilities: the language is in AC^0; it is ACC^0(m)-hard for some m≥2 (hence not in AC^0); or it is constant-depth equivalent to a finite disjoint union of intermediate VPLs, for which membership in AC^0 remains open. The algorithm also computes explicit reductions in the third case, and a corollary states that the procedure decides AC^0 membership exactly for visibly counter languages. Proofs rely on revisiting Ext-algebras and applying Green's relations.

Significance. If the trichotomy is exhaustive and the algorithm correct, the result supplies the first effective classification of AC^0 membership for the full class of visibly pushdown languages, generalizing the decidability result of Krebs et al. for visibly counter languages. The explicit construction of intermediate VPLs and the conjecture that they are uniformly inside or outside AC^0 identify a concrete open problem whose resolution would settle the complexity of an entire family of VPLs. The algebraic machinery (Ext-algebras and Green's relations) is a methodological strength when it yields a decision procedure.

major comments (3)
  1. [Section 4] Main theorem (Section 4, statement of the decision procedure): the proof that the algorithm is exhaustive rests on the claim that Green's relations on the syntactic Ext-algebra of any VPL always place it into one of the three handled cases. No explicit argument is given that every possible J-/R-/L-class combination arising from a VPA is covered; if a syntactic Ext-algebra falls outside the enumerated cases, the trichotomy fails and the algorithm is incomplete.
  2. [Corollary 5.2] Corollary 5.2 (visibly counter languages): the reduction from the main result to the visibly-counter case assumes that no visibly counter language produces an intermediate VPL under the equivalence. The manuscript does not verify this assumption by showing that the syntactic Ext-algebra of a visibly counter automaton never lands in the intermediate case.
  3. [Section 3] Definition of intermediate VPLs (Section 3): the concrete example L(S→ε | a c^{k-1} S b1 | a c^{l-1} S b2) is asserted to be constant-depth reducible to any language in the third output class, yet the reduction is only sketched; the precise constant-depth circuit family realizing the reduction is not exhibited.
minor comments (2)
  1. [Section 3] Notation for the intermediate VPL example uses S as a nonterminal without prior definition in the running text; a short reminder of the grammar convention would improve readability.
  2. The abstract states that the algorithm 'correctly outputs' the three cases, but the manuscript never states the running time or the size of the output Ext-algebra; adding a complexity bound would strengthen the result.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and their constructive comments. We address each of the major comments below.

read point-by-point responses

  1. Referee: [Section 4] Main theorem (Section 4, statement of the decision procedure): the proof that the algorithm is exhaustive rests on the claim that Green's relations on the syntactic Ext-algebra of any VPL always place it into one of the three handled cases. No explicit argument is given that every possible J-/R-/L-class combination arising from a VPA is covered; if a syntactic Ext-algebra falls outside the enumerated cases, the trichotomy fails and the algorithm is incomplete.

    Authors: We agree that the manuscript would benefit from an explicit argument establishing that all possible combinations of Green's relations for syntactic Ext-algebras of VPAs fall into the three cases. In the revised version, we will add a detailed justification based on the structure of Ext-algebras derived from visibly pushdown automata, showing why other combinations cannot occur. revision: yes

  2. Referee: [Corollary 5.2] Corollary 5.2 (visibly counter languages): the reduction from the main result to the visibly-counter case assumes that no visibly counter language produces an intermediate VPL under the equivalence. The manuscript does not verify this assumption by showing that the syntactic Ext-algebra of a visibly counter automaton never lands in the intermediate case.

    Authors: The observation is correct; the corollary relies on this assumption without explicit verification in the current manuscript. We will include a new lemma or subsection proving that visibly counter languages cannot yield intermediate VPLs under the equivalence, by demonstrating that their Ext-algebras satisfy properties incompatible with the intermediate case. revision: yes

  3. Referee: [Section 3] Definition of intermediate VPLs (Section 3): the concrete example L(S→ε | a c^{k-1} S b1 | a c^{l-1} S b2) is asserted to be constant-depth reducible to any language in the third output class, yet the reduction is only sketched; the precise constant-depth circuit family realizing the reduction is not exhibited.

    Authors: We acknowledge that the reduction is sketched rather than fully detailed. In the revised manuscript, we will exhibit the explicit constant-depth circuit family for the reduction from the given example intermediate VPL to the languages in the third class, including the construction of the circuits and the depth and size bounds. revision: yes

Circularity Check

0 steps flagged

No circularity; classification algorithm rests on external Ext-algebra framework

full rationale

The paper's main result is a decision procedure that outputs one of three exhaustive cases for any input VPA, using Ext-algebras (cited to Czarnetzki et al.) and Green's relations to partition languages. No equations, self-definitions, or fitted parameters are shown reducing the trichotomy or the algorithm to the paper's own inputs by construction. The cited algebraic machinery is treated as prior external work, not a self-citation chain or ansatz smuggled from the authors' own prior results. The introduction of intermediate VPLs and the conjecture about them are presented as open questions rather than derived outputs. This satisfies the default expectation of a non-circular paper whose central claim has independent content from external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Review performed on abstract only; the ledger is therefore minimal and provisional.

axioms (1)
  • domain assumption Ext-algebras and Green's relations suffice to decide the three-way classification for any visibly pushdown automaton
    Abstract states that proofs revisit these structures to obtain the algorithm.
invented entities (1)
  • intermediate VPLs no independent evidence
    purpose: A subclass of one-turn visibly pushdown languages for which AC^0 membership status is unknown
    Newly introduced class whose uniform membership in or out of AC^0 is conjectured but unproven.

pith-pipeline@v0.9.0 · 5918 in / 1501 out tokens · 23479 ms · 2026-05-24T10:09:27.524702+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

  1. [1]

    Madhusudan, and Mahesh Visw anathan

    Rajeev Alur, Viraj Kumar, P. Madhusudan, and Mahesh Visw anathan. Congruences for visibly pushdown languages. In Luís Caires, Giuseppe F. Italiano, L uís Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, 32nd International C ollo- quium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proc eedings, volume 3580 of...

    work page doi:10.1007/11523468 2005

  2. [2]

    Madhusudan

    Rajeev Alur and P. Madhusudan. Visibly pushdown languag es. In László Babai, editor, Pro- ceedings of the 36th Annual ACM Symposium on Theory of Comput ing, Chicago, IL, USA, June 13-16, 2004 , pages 202–211. ACM, 2004. doi:10.1145/1007352.1007390

    work page doi:10.1145/1007352.1007390 2004

  3. [3]

    Regula rity problems for visibly pushdown languages

    Vince Bárány, Christof Löding, and Olivier Serre. Regula rity problems for visibly pushdown languages. In Bruno Durand and Wolfgang Thomas, editors, STACS 2006, 23rd Annual Sym- posium on Theoretical Aspects of Computer Science, Marseil le, France, February 23-25, 2006, Proceedings, volume 3884 of Lecture Notes in Computer Science , pages 420–431. Springe...

    work page doi:10.1007/11672142_34 2006

  4. [4]

    Mix Barrington

    David A. Mix Barrington. Bounded-Width Polynomial-Size Br anching Programs Rec- ognize Exactly Those Languages in NC 1. J. Comput. Syst. Sci. , 38(1):150–164, 1989. doi:10.1016/0022-0000(89)90037-8

    work page doi:10.1016/0022-0000(89)90037-8 1989

  5. [5]

    Mix Barrington, Kevin J

    David A. Mix Barrington, Kevin J. Compton, Howard Straubi ng, and Denis Thérien. Regular languages in nc 1. J. Comput. Syst. Sci. , 44(3):478–499, 1992. doi:10.1016/0022-0000(92)90014-A

    work page doi:10.1016/0022-0000(92)90014-a 1992

  6. [6]

    The polynomial method in circuit complex ity

    Richard Beigel. The polynomial method in circuit complex ity. In Proceedings of the Eigth Annual Structure in Complexity Theory Conference, San Dieg o, CA, USA, May 18-21, 1993 , pages 82–95. IEEE Computer Society, 1993. doi:10.1109/SCT.1993.336538

    work page doi:10.1109/sct.1993.336538 1993

  7. [7]

    Forest algebras

    Mikolaj Bojanczyk and Igor Walukiewicz. Forest algebras . In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata: History and Perspectives [in Honor of Wo lfgang Thomas], volume 2 of Texts in Logic and Games , pages 107–132. Amsterdam University Press, 2008

    work page 2008

  8. [8]

    Chandra, Larry J

    Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. C onstant depth reducibility. SIAM J. Comput. , 13(2):423–439, 1984. doi:10.1137/0213028. 80

    work page doi:10.1137/0213028 1984

  9. [9]

    The taming of the s emi-linear set

    Dmitry Chistikov and Christoph Haase. The taming of the s emi-linear set. In Automata, Lan- guages, and Programming, ICALP , volume 55 of LIPIcs, pages 128:1–128:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.128

    work page doi:10.4230/lipics.icalp.2016.128 2016

  10. [10]

    Visibly Pushdown Languages and Free Profinite Algebras

    Silke Czarnetzki, Andreas Krebs, and Klaus-Jörn Lange . Visibly pushdown languages and free profinite algebras. CoRR, abs/1810.12731, 2018. URL: http://arxiv.org/abs/1810.12731, arXiv:1810.12731

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  11. [11]

    Patrick W. Dymond. Input-driven languages are in log n d epth. Inf. Process. Lett., 26(5):247– 250, 1988. doi:10.1016/0020-0190(88)90148-2

    work page doi:10.1016/0020-0190(88)90148-2 1988

  12. [12]

    Automata, Languages, and Machines

    Samuel Eilenberg. Automata, Languages, and Machines. Volume A . Pure and applied mathematics. Academic Press, New York, 1974. UR L: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/59/part/PA

    work page 1974

  13. [13]

    Automata, Languages, and Machines

    Samuel Eilenberg. Automata, Languages, and Machines. Volume B . Pure and applied mathematics. Academic Press, New York, 1976. UR L: https://www.sciencedirect.com/bookseries/pure-and-applied-mathematics/vol/59/part/PB

    work page 1976

  14. [14]

    Parikh’s theorem: A simple and direct automaton construction

    Javier Esparza, Pierre Ganty, Stefan Kiefer, and Micha el Luttenberger. Parikh’s theorem: A simple and direct automaton construction. Inf. Process. Lett. , 111(12):614–619, 2011. doi:10.1016/j.ipl.2011.03.019

    work page doi:10.1016/j.ipl.2011.03.019 2011

  15. [15]

    A brief history of strahler numbers

    Javier Esparza, Michael Luttenberger, and Maximilian Schlund. A brief history of strahler numbers. In Adrian-Horia Dediu, Carlos Martín-Vide, José L uis Sierra-Rodríguez, and Bianca Truthe, editors, Language and Automata Theory and Applications - 8th Interna tional Con- ference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proce edings, volume 8370 of Lec...

    work page doi:10.1007/978-3-319-04921-2 2014

  16. [16]

    Yuri Gurevich and Harry R. Lewis. A logic for constant-d epth circuits. Inf. Control., 61(1):65– 74, 1984. doi:10.1016/S0019-9958(84)80062-5

    work page doi:10.1016/s0019-9958(84)80062-5 1984

  17. [17]

    Harrison

    Michael A. Harrison. Introduction to Formal Language Theory . Addison-Wesley, 1978

    work page 1978

  18. [18]

    Almost optimal lower bounds for small depth circuits

    Johan Håstad. Almost optimal lower bounds for small dep th circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Com puting, May 28-30, 1986, Berkeley, California, USA , pages 6–20. ACM, 1986. doi:10.1145/12130.12132

    work page doi:10.1145/12130.12132 1986

  19. [19]

    Languages that capture complexity clas ses

    Neil Immerman. Languages that capture complexity clas ses. SIAM J. Comput. , 16(4):760–778,

    work page

  20. [20]

    Descriptive Complexity

    Neil Immerman. Descriptive complexity . Graduate texts in computer science. Springer, 1999. doi:10.1007/978-1-4612-0539-5

    work page doi:10.1007/978-1-4612-0539-5 1999

  21. [21]

    Boolean Function Complexity - Advances and Frontiers , volume 27 of Algorithms and combinatorics

    Stasys Jukna. Boolean Function Complexity - Advances and Frontiers , volume 27 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-24508-4

    work page doi:10.1007/978-3-642-24508-4 2012

  22. [22]

    V isibly counter languages and constant depth circuits

    Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. V isibly counter languages and constant depth circuits. In Ernst W. Mayr and Nicolas Ollinger, edito rs, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, Mar ch 4-7, 2015, Garching, Ger- many, volume 30 of LIPIcs, pages 594–607. Schloss Dagstuhl - Leibniz-Zentrum für ...

    work page 2015

  23. [23]

    doi:10.4230/LIPIcs.STACS.2015.594. 81

    work page doi:10.4230/lipics.stacs.2015.594 2015

  24. [24]

    Tree-Structured Problems and Parallel Computa- tion

    Michael Ludwig. Tree-Structured Problems and Parallel Computa- tion. PhD thesis, University of Tübingen, Germany, 2019. URL: https://publikationen.uni-tuebingen.de/xmlui/handle/10900/85960/

    work page 2019

  25. [25]

    Pebbling Moutain Ranges and its Applica tion of DCFL-Recognition

    Kurt Mehlhorn. Pebbling Moutain Ranges and its Applica tion of DCFL-Recognition. In J. W. de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming, 7th Collo- quium, Noordweijkerhout, The Netherlands, July 14-18, 198 0, Proceedings, volume 85 of Lecture Notes in Computer Science , pages 422–435. Springer, 1980. doi:10.1007/3-540-10003-2\_89

    work page doi:10.1007/3-540-10003-2 1980

  26. [26]

    Varieties of Formal Languages

    Jean-Éric Pin. Varieties of Formal Languages . North Oxford, London and Plenum, New-York,

    work page

  27. [27]

    (Traduction de Variétés de langages formels)

    work page

  28. [28]

    Handbook of Automata Theory

    Jean-Éric Pin, editor. Handbook of Automata Theory . European Mathematical Society Pub- lishing House, Zürich, Switzerland, 2021. doi:10.4171/Automata

    work page doi:10.4171/automata 2021

  29. [29]

    On finite monoids having on ly trivial subgroups

    Marcel Paul Schützenberger. On finite monoids having on ly trivial subgroups. Inf. Control. , 8(2):190–194, 1965. doi:10.1016/S0019-9958(65)90108-7

    work page doi:10.1016/s0019-9958(65)90108-7 1965

  30. [30]

    Finite Automata, Formal Logic, and Circuit Complexity

    Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity . Birkhäuser Boston,

    work page

  31. [31]

    doi:10.1007/978-1-4612-0289-9

    work page doi:10.1007/978-1-4612-0289-9

  32. [32]

    On logical descriptions of regular l anguages

    Howard Straubing. On logical descriptions of regular l anguages. In Sergio Rajsbaum, editor, LATIN 2002: Theoretical Informatics, 5th Latin American Sy mposium, Cancun, Mexico, April 3-6, 2002, Proceedings , volume 2286 of Lecture Notes in Computer Science , pages 528–538. Springer, 2002. doi:10.1007/3-540-45995-2\_46

    work page doi:10.1007/3-540-45995-2 2002

  33. [33]

    Introduction to Circuit Complexity - A Uniform Approach

    Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach . Texts in Theoret- ical Computer Science. An EATCS Series. Springer, 1999. doi:10.1007/978-3-662-03927-4 . 82

    work page doi:10.1007/978-3-662-03927-4 1999