Rational Reductions and Regular Languages of Constant Circuit Complexity

Amaldev Manuel; Stefan G\"oller

REVIEW

Rational Reductions and Regular Languages of Constant Circuit Complexity

Stefan Göller, Amaldev Manuel

Computational Complexity · Submitted 16 Sep 2026 · 37 references

Pith's verdict: Characterizes constant circuit complexity for regular languages from five directions; proof chain looks sound, but the subset-encoding choice and sketchy PSPACE upper bound give honest conditional verdict.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 17, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.18484 (version 1)

Pith ID4DTC3FWJ, Pith's permanent record of this paper and its review

CitationAmaldev Manuel, Stefan G\"oller. "Rational Reductions and Regular Languages of Constant Circuit Complexity." arXiv:2609.18484 (2026). https://pith.science/paper/4DTC3FWJ

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Stefan and Amaldev have done something clean here. The result is a five-way characterization of regular languages of constant circuit complexity under the subset encoding: algebraic (QEJ1 identities), logical (FO1[Σ,arb]), by congruences (≈_k), by regular expressions (Cont_k), and the collapse of o(log n) to O(1). The hard direction—sublogarithmic implies constant—is handled with a transparent pigeonhole argument that avoids heavy machinery. The rational truth-table reduction framework is a nice technical tool and is likely to be reused. The PSPACE-completeness of O(1)-membership is a natural bonus.

What the paper does well: it gives a fully worked equivalence chain (1)⇒(2)⇒...⇒(9)⇒(1) that the reader verified. The lower bound (Proposition 4.22) is the clearest part; the algebra-to-congruence direction (Proposition 4.24) is correctly supported by the idempotent identities. The authors are upfront about the modeling choice: the subset encoding (Definition 2.2) is equivalent to one-hot with promise, and they explicitly show that one-hot without promise behaves differently (Proposition 6.18). No circularity, no missing references.

Soft spots, in proportion. The PSPACE upper bound (Proposition 5.2) is presented as a sketch—Claims 1–3 are described but not machine-checked. This is typical for a conference paper, but for a full classification one might want more detail. Two side assertions (QEJ1 = EJ1 * Mod, and the Θ refinements in Example 4.15) are stated without proof; they are not load-bearing, but they leave small loose ends. The main dependency on the subset encoding is the most fragile premise: if a reader insists on one-hot without promise, the classification fails. The authors acknoledge this, but it does limit the universality of the result.

Overall, this is a solid piece of work that closes a natural gap in the circuit hierarchy of regular languages. It deserves a serious referee. I would bring it to reading group and would cite the collapse result. The conditional verdict is appropriate—the missing proofs for the PSPACE upper bound and side claims are the main reasons to hold back today.

Referee report

Major objections (2)

[§5.1] The PSPACE upper bound is presented as a sketch (verifying the identities of QEJ1 on the fly). While the algorithm is plausible, the exposition is quite compressed; for a journal publication, a more detailed description of the polynomial-space decision procedure, including the handling of the existential quantifiers in Claims 1–3, would strengthen the self-containedness of the paper.
[§6.2, Proposition 6.18] The paper correctly acknowledges the non-robustness of the one-hot encoding without promise. However, the statement that the class under the one-hot encoding is 'not an lm-variety' is supported by only two specific counterexamples (complement and inverse morphism). Could the authors briefly argue that no alternative definition of circuit complexity for regular languages can yield both closure properties, or is this intended as a cautionary observation? A short remark would clarify the scope of the main classification.

Minor objections (6)

[Abstract & §1] 'PSP ACE' should be typeset as 'PSPACE' (missing space).
[§4.4, Theorem 4.14] In the statement of condition (5), 'uCont_k(Γ_0,…,Γ_{k-1})v' appears without parentheses; consider writing 'u·Cont_k(Γ_0,…,Γ_{k-1})·v' for clarity.
[§4.5, Proposition 4.22] The pigeonhole argument uses log_{2^{2|Γ|}}(n/6). The derivation of the base 2^{2|Γ|} from the number of possible connections could be explained in one sentence to help the reader.
[§3.1, Definition 3.1] The term 'rational truth-table reduction' is central but the motivation for the name is not given; a brief remark linking it to 'rational' (length-multiplying morphisms) and 'truth-table' (Boolean combination) would be helpful.
[§4.6, Lemma 4.27] The proof uses the notation '=_{φ}' to mean equality under φ; define this explicitly earlier to avoid confusion.
[General] There are occasional extra spaces in logical notation (e.g., 'FO 1[Σ,arb]' should be 'FO^1[Σ,arb]' and 'PSP ACE' appears a few times).

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Regular languages of constant circuit complexity characterized from algebra, logic, and combinatorics.

The reading

This paper establishes a complete characterization of regular languages that can be recognized by Boolean circuit families of constant size (unbounded fan-in). It shows that for regular languages, having circuit complexity O(1) is equivalent to having sublogarithmic circuit complexity o(log n)—there is no intermediate regime. The characterization is given from five perspectives: the syntactic morphism lies in the pseudovariety QEJ_1 of finite semigroups; the language is a union of classes of the congruence ≈_k; the language is a finite Boolean combination of finite languages and languages of the form u(Γ_0...Γ_{k-1})^+ v; the language is definable in the one-variable fragment of first-order logic with arbitrary numerical predicates; and a simple combinatorial description via modular counting of letters. The paper also shows that deciding whether a regular language given by an NFA has constant circuit complexity is PSPACE-complete.

What carries the argument

The key machinery is the pseudovariety QEJ_1 of stamps whose stable semigroup satisfies the identities epxqf = epxxqf and epxyqf = epyxqf (where e,f range over idempotents and p,q,x,y over any elements). This algebraic condition is shown to be equivalent to the combinatorial congruence ≈_k, which identifies two words if they have the same k-length prefix and suffix, the same length modulo k, and the same letter counts per residue class modulo k. The paper also introduces rational truth-table reductions, a strong form of reduction that preserves circuit complexity bounds for mild functions.

Extended reading notes

Core claim

The central discovery is that the circuit complexity of a regular language is either constant or at least logarithmic: there is no sublogarithmic but non-constant regime. The paper proves this by showing that if the stable semigroup of the syntactic morphism does not satisfy the identities epxqf = epxxqf and epxyqf = epyxqf, then the language requires at least logarithmically many gates. Conversely, if the identities hold, the language has a constant-size circuit family. The classification is robust, yielding equivalent descriptions in algebra, logic, regular expressions, and combinatorics.

Load-bearing premise

The entire classification depends on the choice of the subset encoding for circuit inputs (Definition 2.2), which is equivalent to the one-hot encoding with a well-formedness promise. Under the standard one-hot encoding without the promise, the class of constant-circuit regular languages is not closed under complement or inverse length-multiplying morphisms, thus not an lm-variety, and the algebraic characterization fails.

Editorial extensions

If this is right

Every regular language not in QEJ_1 has circuit complexity at least logarithmic, providing a tight lower bound.
The one-variable fragment of first-order logic with arbitrary numerical predicates (FO^1[Σ,arb]) captures exactly the regular languages of constant circuit complexity.
The problem of determining whether a given NFA accepts a language of constant circuit complexity is PSPACE-complete, reflecting the difficulty of computing the stable semigroup identities.
The rational truth-table reductions developed here apply to any class of languages whose circuit complexity is bounded by a mild function, making them a general tool for circuit lower bounds.
The characterization implies that the regular languages of constant circuit complexity form a length-multiplying variety of languages, enabling algebraic methods for circuit analysis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The collapse of sublogarithmic complexity to constant complexity suggests that any regular language requiring super-constant but sublogarithmic circuit size would be a counterexample; none exists.
The logical characterization via FO^1[Σ,arb] implies that constant-size circuits for regular languages can be transformed into one-variable first-order sentences, potentially linking circuit design to model theory.
The identification of the congruence ≈_k may have applications in learning theory: constant-circuit languages are those where membership only depends on bounded prefix/suffix information and modular letter counts.

Original abstract

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,576 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.24 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.92 · compares with prior results 0.19 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families.	contribution 0.56	0.77	0.04	asserted 0.84
s1	We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions.	result 0.74	0.93	0.53	asserted 1.00
s2	We analogously characterize the neutral letter regular languages of constant circuit complexity.	contribution 0.60	0.94	0.06	asserted 0.99
s3	Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity.	result 0.58	0.91	0.25	asserted 0.99
s4	In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete.	result 0.97	0.95	0.10	asserted 1.00
s5	We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages.	contribution 0.86	0.95	0.05	asserted 0.99
s6	We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity.	result 0.93	0.96	0.10	asserted 1.00
s7	We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages.	result 0.98	0.95	0.10	asserted 1.00
s8	Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$.	contribution 0.64	0.95	0.08	asserted 1.00
s9	For these we derive logarithmic circuit complexity upper bounds.	result 1.00	0.94	0.08	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Product & Division of Stamps If V is a variety of semigroups, then the collection of all stamps whose stable semigroup is in V forms an lm-pseudovariety of stamps, denoted by QV [33]. 3.5 Identities on Semigroups An identity is an equation t = t ′ , where t and t ′ are finite words built from a set of variables using multiplication and ω-power. For example xy = yx, x = x ω , and (xyω z) ω = xyω are all identities. A semigroup S satisfies the identity t = t ′ if the two sides evaluate to the same element under every assignment of the variables to elements of S. For instance, th

**Figure 2.** Syntactic and stable semigroups of L1 = (ab) +. The stability index of ηL1 is two. stab(ηL1 ) is in J1, hence ηL1 is in QEJ1. b * a *

**Figure 4.** Syntactic and stable semigroup of L3 = a +b +. The stability index of ηL3 is two. stab(ηL3 ) is not in EJ1 since aaabbb = ab ̸= ba = aababb. Hence ηL3 is not in QEJ1. b * a aa *

**Figure 6.** The word u = u ′u ′′ Note that u ′ = x −1uy−1 = x ′κk(u)y ′ and v ′ = x −1vy−1 = x ′κk(v)y ′ , where x ′ = x −1αk(u) = x −1αk(v) and y ′ = ωk(u)y −1 = ωk(v)y −1 . Since u ≈k v implies κk(u) C 1 k κk(v) and since C 1 k is a congruence by Point (1) of Lemma 4.4 we have u ′ = x ′κk(u)y ′ C 1 k x ′κk(v)y ′ = v ′ . Since s|k we also have u ′ C 1 s v ′ by Point (2) of Lemma 4.4. Recalling that the lengths of u ′ and v ′ are both divisible by s we therefore have pu′p =φ pv′p by Lemma 4.28. We are now ready to prove Proposition 4.24. 4.6.1 Proof of Proposition 4.24 Proof. Let k = sN. By…

Showing 4 of the paper's 6 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:2609.18484 by the authors.

References

Works cited (37)

[1]

Sanjeev Arora and Boaz Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2009

View on Pith 2009
[2]

David A. Barrington. Bounded-Width Polynomial-Size Branching Programs Recog- nize Exactly Those Languages in NC1.Journal of Computer and System Sciences, 38(1):150–164, 1989

View on Pith 1989
[3]

David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular Languages in NC1.J. Comput. Syst. Sci., 44(3):478–499, 1992

View on Pith 1992
[4]

David A. Mix Barrington and Denis Thérien. Finite Monoids and the Fine Structure ofNC 1.Journal of the ACM, 35(4):941–952, October 1988. 60

View on Pith 1988
[5]

Michaël Cadilhac and Charles Paperman. The regular languages of wire linear AC0. Acta Informatica, 59(4):321–336, 2022

View on Pith 2022
[6]

Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423–439, 1984

View on Pith 1984
[7]

L. Chaubard, J. Pin, and H. Straubing. First Order Formulas with Modular Predicates. In21st Annual IEEE Symposium on Logic in Computer Science (LICS’06), pages 211– 220, 2006

View on Pith 2006
[8]

Laura Chaubard, Jean Éric Pin, and Howard Straubing. Actions, wreath products of C-varieties and concatenation product.Theoretical Computer Science, 356(1):73–89,

View on Pith
[9]

Luc Dartois and Charles Paperman. Two-variable first order logic with modular pred- icates over words. InSTACS 2013, volume 20 ofLIPIcs, pages 329–340, Dagstuhl, Germany, 2013

View on Pith 2013
[10]

Volker Diekert, Paul Gastin, and Manfred Kufleitner. A Survey on Small Fragments of First-Order Logic over Finite Words.Int. J. Found. Comput. Sci., 19:513–548, 06 2008

View on Pith 2008
[11]

Samuel Eilenberg.Automata, Languages, and Machines, Volume B, volume 59 ofPure and Applied Mathematics. Academic Press, 1976. Includes chapters by Bret Tilson

View on Pith 1976
[12]

Javier Esparza and Michael Blondin.Automata Theory: An Algorithmic Approach. MIT Press, 2023

View on Pith 2023
[13]

Nathanaël Fijalkow and Charles Paperman. Monadic Second-Order Logic with Arbi- trary Monadic Predicates.ACM Trans. Comput. Logic, 18(3), August 2017

View on Pith 2017
[14]

JoelFriedman. ConstructingO(nlogn)SizeMonotoneFormulaeforthek-thThreshold Function of n Boolean Variables.SIAM J. Comput., 15(3):641–654, 1986

View on Pith 1986
[15]

Merrick Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy.Mathematical Systems Theory, 17(1):13–27, 1984

View on Pith 1984
[16]

Nathan Grosshans. The Power of Programs over Monoids inJ. InLanguage and Automata Theory and Applications, pages315–327, Cham, 2020.SpringerInternational Publishing. 61

View on Pith 2020
[17]

Nathan Grosshans. A Note on the Join of Varieties of Monoids with LI. InMFCS 2021, LIPIcs, pages 51:1–51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021

View on Pith 2021
[18]

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Tameness and the power of programs over monoids in DA.Log. Methods Comput. Sci., 18(3), 2022

View on Pith 2022
[19]

J. Hastad, I. Wegener, N. Wurm, and S.Z. Yi. Optimal Depth, Very Small Size Circuits for Symmetrical Functions inAC 0.Information and Computation, 108(2):200–211, 1994

View on Pith 1994
[20]

Juraj Hromkovic. Linear Lower Bounds on Unbounded Fan-In Boolean Circuits.Inf. Process. Lett., 21(2):71–74, 1985

View on Pith 1985
[21]

Michal Koucký. Circuit Complexity of Regular Languages.Theory of Computing Systems, 45(4):865–879, 2009

View on Pith 2009
[22]

Michal Koucký. Circuit complexity of regular languages. In Jean-Éric Pin, editor, Handbook of Automata Theory, pages 493–523. European Mathematical Society Pub- lishing House, Zürich, Switzerland, 2021

View on Pith 2021
[23]

Manfred Kufleitner and Tobias Walter. One quantifier alternation in first-order logic with modular predicates.RAIRO Theor. Informatics Appl., 49(1):1–22, 2015

View on Pith 2015
[24]

Michal Kunc. Equational description of pseudovarieties of homomorphisms.RAIRO - Theoretical Informatics and Applications, 37(3):243–254, 3 2003

View on Pith 2003
[25]

Pierre McKenzie, Pierre Péladeau, and Denis Therien.NC1: The automata-theoretic viewpoint.computational complexity, 1(4):330–359, 1991

View on Pith 1991
[26]

Robert McNaughton and Seymour Papert.Counter-Free Automata. The MIT Press, Cambridge, MA, 1971

View on Pith 1971
[27]

Jean-Éric Pin.Handbook of Automata Theory. European Mathematical Society Pub- lishing House, September 2021

View on Pith 2021
[28]

Jean-Éric Pin.Mathematical Foundations of Automata Theory, 2025. Lecture notes, MPRI, Université Paris and IRIF

View on Pith 2025
[29]

Jean-ÉricPinandHowardStraubing. SomeresultsonC-varieties.RAIRO - Theoretical Informatics and Applications, 39(1):239–262, 3 2005. 62

View on Pith 2005
[30]

Pierre Péladeau, Howard Straubing, and Denis Therien. Finite semigroup varieties defined by programs.Theoretical Computer Science, 180(1):325–339, 1997

View on Pith 1997
[31]

Marcel-Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups.In- formation and Control, 8:190–194, 1965

View on Pith 1965
[32]

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

View on Pith 1994
[33]

HowardStraubing. OnLogicalDescriptionsofRegularLanguages. InSergioRajsbaum, editor,LATIN 2002: Theoretical Informatics, pages 528–538, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg

View on Pith 2002
[34]

Pascal Tesson and Denis Therien. Bridges between algebraic automata theory and complexity theory.Bulletin of the European Association for Theoretical Computer Science EATCS, 01 2006

View on Pith 2006
[35]

PascalTessonandDenisTherien. LogicMeetsAlgebra: theCaseofRegularLanguages. Logical Methods in Computer Science, Volume 3, Issue 1, Feb 2007

View on Pith 2007
[36]

Paul M. B. Vitányi and Lambert G. L. T. Meertens. Big omega versus the wild functions.Bull. EATCS, 22:14–19, 1984. 63 A Proofs for Section 3 (Reductions & Varieties of Recogniz- able Languages) Proposition 3.2(Commuting operations).We observe the following commutativities of operations. (1)Inverse (length-multiplying) morphisms and Boolean operations comm...

View on Pith 1984
[2006]

In honour of Professor Christian Choffrut on the occasion of his 60th birthday

View on Pith

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Sanjeev Arora and Boaz Barak.Computational Complexity: A Modern Approach. Cambridge University Press, 2009

View on Pith 2009

[2] [2]

David A. Barrington. Bounded-Width Polynomial-Size Branching Programs Recog- nize Exactly Those Languages in NC1.Journal of Computer and System Sciences, 38(1):150–164, 1989

View on Pith 1989

[3] [3]

David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular Languages in NC1.J. Comput. Syst. Sci., 44(3):478–499, 1992

View on Pith 1992

[4] [4]

David A. Mix Barrington and Denis Thérien. Finite Monoids and the Fine Structure ofNC 1.Journal of the ACM, 35(4):941–952, October 1988. 60

View on Pith 1988

[5] [5]

Michaël Cadilhac and Charles Paperman. The regular languages of wire linear AC0. Acta Informatica, 59(4):321–336, 2022

View on Pith 2022

[6] [6]

Ashok K. Chandra, Larry J. Stockmeyer, and Uzi Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423–439, 1984

View on Pith 1984

[7] [7]

L. Chaubard, J. Pin, and H. Straubing. First Order Formulas with Modular Predicates. In21st Annual IEEE Symposium on Logic in Computer Science (LICS’06), pages 211– 220, 2006

View on Pith 2006

[8] [8]

Laura Chaubard, Jean Éric Pin, and Howard Straubing. Actions, wreath products of C-varieties and concatenation product.Theoretical Computer Science, 356(1):73–89,

View on Pith

[9] [9]

Luc Dartois and Charles Paperman. Two-variable first order logic with modular pred- icates over words. InSTACS 2013, volume 20 ofLIPIcs, pages 329–340, Dagstuhl, Germany, 2013

View on Pith 2013

[10] [10]

Volker Diekert, Paul Gastin, and Manfred Kufleitner. A Survey on Small Fragments of First-Order Logic over Finite Words.Int. J. Found. Comput. Sci., 19:513–548, 06 2008

View on Pith 2008

[11] [11]

Samuel Eilenberg.Automata, Languages, and Machines, Volume B, volume 59 ofPure and Applied Mathematics. Academic Press, 1976. Includes chapters by Bret Tilson

View on Pith 1976

[12] [12]

Javier Esparza and Michael Blondin.Automata Theory: An Algorithmic Approach. MIT Press, 2023

View on Pith 2023

[13] [13]

Nathanaël Fijalkow and Charles Paperman. Monadic Second-Order Logic with Arbi- trary Monadic Predicates.ACM Trans. Comput. Logic, 18(3), August 2017

View on Pith 2017

[14] [14]

JoelFriedman. ConstructingO(nlogn)SizeMonotoneFormulaeforthek-thThreshold Function of n Boolean Variables.SIAM J. Comput., 15(3):641–654, 1986

View on Pith 1986

[15] [15]

Merrick Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy.Mathematical Systems Theory, 17(1):13–27, 1984

View on Pith 1984

[16] [16]

Nathan Grosshans. The Power of Programs over Monoids inJ. InLanguage and Automata Theory and Applications, pages315–327, Cham, 2020.SpringerInternational Publishing. 61

View on Pith 2020

[17] [17]

Nathan Grosshans. A Note on the Join of Varieties of Monoids with LI. InMFCS 2021, LIPIcs, pages 51:1–51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021

View on Pith 2021

[18] [18]

Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Tameness and the power of programs over monoids in DA.Log. Methods Comput. Sci., 18(3), 2022

View on Pith 2022

[19] [19]

J. Hastad, I. Wegener, N. Wurm, and S.Z. Yi. Optimal Depth, Very Small Size Circuits for Symmetrical Functions inAC 0.Information and Computation, 108(2):200–211, 1994

View on Pith 1994

[20] [20]

Juraj Hromkovic. Linear Lower Bounds on Unbounded Fan-In Boolean Circuits.Inf. Process. Lett., 21(2):71–74, 1985

View on Pith 1985

[21] [21]

Michal Koucký. Circuit Complexity of Regular Languages.Theory of Computing Systems, 45(4):865–879, 2009

View on Pith 2009

[22] [22]

Michal Koucký. Circuit complexity of regular languages. In Jean-Éric Pin, editor, Handbook of Automata Theory, pages 493–523. European Mathematical Society Pub- lishing House, Zürich, Switzerland, 2021

View on Pith 2021

[23] [23]

Manfred Kufleitner and Tobias Walter. One quantifier alternation in first-order logic with modular predicates.RAIRO Theor. Informatics Appl., 49(1):1–22, 2015

View on Pith 2015

[24] [24]

Michal Kunc. Equational description of pseudovarieties of homomorphisms.RAIRO - Theoretical Informatics and Applications, 37(3):243–254, 3 2003

View on Pith 2003

[25] [25]

Pierre McKenzie, Pierre Péladeau, and Denis Therien.NC1: The automata-theoretic viewpoint.computational complexity, 1(4):330–359, 1991

View on Pith 1991

[26] [26]

Robert McNaughton and Seymour Papert.Counter-Free Automata. The MIT Press, Cambridge, MA, 1971

View on Pith 1971

[27] [27]

Jean-Éric Pin.Handbook of Automata Theory. European Mathematical Society Pub- lishing House, September 2021

View on Pith 2021

[28] [28]

Jean-Éric Pin.Mathematical Foundations of Automata Theory, 2025. Lecture notes, MPRI, Université Paris and IRIF

View on Pith 2025

[29] [29]

Jean-ÉricPinandHowardStraubing. SomeresultsonC-varieties.RAIRO - Theoretical Informatics and Applications, 39(1):239–262, 3 2005. 62

View on Pith 2005

[30] [30]

Pierre Péladeau, Howard Straubing, and Denis Therien. Finite semigroup varieties defined by programs.Theoretical Computer Science, 180(1):325–339, 1997

View on Pith 1997

[31] [31]

Marcel-Paul Schützenberger. On Finite Monoids Having Only Trivial Subgroups.In- formation and Control, 8:190–194, 1965

View on Pith 1965

[32] [32]

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

View on Pith 1994

[33] [33]

HowardStraubing. OnLogicalDescriptionsofRegularLanguages. InSergioRajsbaum, editor,LATIN 2002: Theoretical Informatics, pages 528–538, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg

View on Pith 2002

[34] [34]

Pascal Tesson and Denis Therien. Bridges between algebraic automata theory and complexity theory.Bulletin of the European Association for Theoretical Computer Science EATCS, 01 2006

View on Pith 2006

[35] [35]

PascalTessonandDenisTherien. LogicMeetsAlgebra: theCaseofRegularLanguages. Logical Methods in Computer Science, Volume 3, Issue 1, Feb 2007

View on Pith 2007

[36] [36]

Paul M. B. Vitányi and Lambert G. L. T. Meertens. Big omega versus the wild functions.Bull. EATCS, 22:14–19, 1984. 63 A Proofs for Section 3 (Reductions & Varieties of Recogniz- able Languages) Proposition 3.2(Commuting operations).We observe the following commutativities of operations. (1)Inverse (length-multiplying) morphisms and Boolean operations comm...

View on Pith 1984

[37] [2006]

In honour of Professor Christian Choffrut on the occasion of his 60th birthday

View on Pith