Rational Reductions and Regular Languages of Constant Circuit Complexity

Bounds on Circuit Size; Length-Multiplying Pseudovarieties

• Regular languages provide witnesses separating circuit classes, while prior work connects AC0 to aperiodic stable semigroups and first-order logic.The paper frames circuit size as total computational cost and motivates regular languages as a bridge between sequential and parallel computation.Source: §1 · p. 4, Length-Multiplying Pseudovarieties · pp. 10–11

Programs over Monoids; 1.3 Organization of this paper

• The paper situates its characterizations in the framework of length-multiplying varieties and notes that QEJ1 has also been studied for programs over monoids.Source: §1 · p. 5, Programs over Monoids · p. 11, §1.3 · p. 11

Circuit Model and Input Encodings

• For regular languages recognized with a one-hot encoding without promise, constant circuit complexity is not closed under complement or inverse length-multiplying morphisms.With promise, the subset and one-hot models are equivalent in their circuit-size bounds.Source: Circuit Model and Input Encodings · p. 6

Rational Truth-Table Reductions

• Rational truth-table reductions preserve upper and lower circuit-complexity bounds for mild functions, and mild-bounded regular-language classes form length-multiplying varieties.Source: Rational Truth-Table Reductions · pp. 6–7

O(1)-Characterization Theorem

• Constant circuit complexity is equivalent to sublogarithmic complexity and to the syntactic morphism satisfying the QEJ1 identities.The paper also characterizes these languages through word congruences, one-variable logic with arbitrary numerical predicates, and regular-expression descriptions.Source: O(1)-Characterization Theorem · p. 7

O(1)-Characterization Theorem For Neutral Letter Regular Languages

• Neutral-letter regular languages have constant circuit complexity exactly when they are idempotent and commutative, alphabetic, definable in FO1[Σ], or finite Boolean combinations of Γ* languages.Source: O(1)-Characterization Theorem For… · p. 8

Decidability of O(1)-Membership

• Deciding whether an NFA recognizes a language of constant circuit complexity is PSPACE-complete.The upper bound checks QEJ1 identities on the fly using representatives of the stable semigroup and transition matrices.Source: Decidability of O(1)-Membership · p. 8

Characterization and Complexity of QEACom

• The paper characterizes QEACom languages through syntactic-semigroup identities, counting-based language forms, and C1[Σ, arb] definability.The introduction identifies threshold languages as members of this class; the paper states that a circuit upper bound follows from prior results.Source: Characterization and Complexity of… · p. 9

2.1 Words and Languages

• A word’s positions are indexed from 0, its alphabetic content is the set of letters appearing in it, and prefixes, suffixes, factors, and quotients provide basic word operations.Unless stated otherwise, the paper works with positive languages, which exclude the empty word.Source: §2.1 · p. 12

2.2 Recognition by Finite Semigroups

• A stamp is a surjective semigroup morphism from nonempty words over a finite alphabet to a finite semigroup; length-multiplying morphisms map every letter to a word of one fixed positive length.The composition of two length-multiplying morphisms is also length-multiplying.Source: §2.2 · p. 13
• The syntactic congruence identifies words that remain indistinguishable for membership in every left and right context, yielding the language’s syntactic semigroup.The canonical morphism into this semigroup is called the syntactic morphism or syntactic stamp.Source: §2.2 · p. 13
• Regular languages are recognizable by finite semigroups, equivalently by finite-state automata or regular expressions.A language is recognized when a morphism into a finite semigroup maps it to a designated subset.Source: §2.2 · pp. 13–14

2.3 Circuit Complexity

• Circuit complexity is the minimum non-input gate count of an n-circuit computing the language’s length-n words, with families nonuniform and gates of unbounded fan-in.Every regular language has a circuit family of linear size and logarithmic depth.Source: §2.3 · pp. 15–16

2.4 First-Order Logic Over Words

• First-order formulas interpret words as ordered positions with letter predicates and numerical predicates such as order, successor, and modular position.FO1 uses only the variable x; the examples define (ab)+ using modular predicates and a singleton word using successor relations.Source: §2.4 · pp. 16–17

3.1 Reductions for Recognizable Languages

• Rational truth-table reductions combine inverse length-multiplying morphisms, two-sided quotients, and finite Boolean combinations; these operations commute in the stated ways.The two canonical cases are inverse length-multiplying morphisms and finite Boolean combinations of two-sided quotients.Source: §3.1 · pp. 18–19
• For mild functions, rational truth-table reductions preserve both O(f) circuit upper bounds and Ω(f) lower bounds.Mild functions include eventually positive constants, nondecreasing eventually positive polynomials, and logarithmic powers, but not 2^n.Source: §3.1 · p. 21

3.2 Reductions and Stamps

• For a regular language L, each stable-semigroup element x has a language Kx over fixed-length blocks that rationally truth-table reduces to L.Kx is recognized by evaluating the flattened blocks with L’s syntactic morphism.Source: §3.2 · p. 24

3.3 Circuits & Length-Multiplying Varieties of Languages

• The regular languages with O(1), O(log^k n), or O(n^ε) circuit size form length-multiplying varieties.The closure result concerns the intersections of those size classes with the regular languages.Source: §3.3 · p. 25

3.4 Length-Multiplying Pseudovarieties of Stamps

• Length-multiplying pseudovarieties of stamps correspond one-to-one with length-multiplying varieties of languages.The stamp-side operations are finite diagonal direct products and length-multiplying divisions.Source: §3.4 · p. 25

3.5 Identities on Semigroups

• Semigroup identities are equations in variables using multiplication and ω-power, and are satisfied when both sides evaluate equally under every variable assignment.Variables e, f, and so on are conventionally used for idempotent elements.Source: §3.5 · p. 26

4 The Regular Languages of Constant Circuit Complexity

• If a regular language’s syntactic stamp is outside QEJ1, its circuit complexity is Ω(log n); inside QEJ1, the language is a finite union of ≈k classes for some k.The section presents these as the two difficult directions of the O(1) characterization theorem.Source: §4 · pp. 26–27

4.1 The Modular Threshold-Counting Congruence Ct

• The congruence Ct_k compares words by length modulo k and by their modular threshold-counting profiles.The profile records which letters occur with counts satisfying the specified modular and threshold conditions.Source: §4.1 · p. 27

4.2 The O(1) Congruence

• For words longer than 2k, αk and ωk denote the length-k prefix and suffix, while κk is the intervening factor when the word is longer than 2k.The refined congruence is introduced for characterizing regular languages with constant circuit complexity.Source: §4.2 · pp. 27–28

4.3 The Pseudovariety EJ1

• A stamp belongs to QEJ1 when its stable semigroup belongs to EJ1.EJ1 is defined by identities, though their full statement is not included in these passages.Source: §4.3 · p. 28
• The stable semigroups for (ab)+ and b∗a(a + b)∗ lie in J1, and therefore their syntactic stamps belong to QEJ1.Their stability indices are two and one, respectively.Source: §4.3 · p. 28, Figure 2 · p. 29, Figure 3 · p. 29
• The stable semigroups for a+b+ and b∗ab∗a(a + b)∗ fail identities of EJ1, so their syntactic stamps are not in QEJ1.The section supplies distinct identity violations for the two examples.Source: §4.3 · p. 29, Figure 4 · p. 30, Figure 5 · p. 30
• A finite semigroup belongs to EJ1 exactly when words with the same content after removing e and f evaluate equally between e and f.The condition is stated for all words u and v and elements e and f.Source: §4.3 · p. 29

4.4 O(1) Characterization Theorem

• For regular languages, sublogarithmic circuit complexity is equivalent to constant circuit complexity and to definability in FO1[Σ, reg] and FO1[Σ, arb].The theorem also gives algebraic, congruence, and regular-expression characterizations.Source: §4.4 · p. 31
• The theorem characterizes these languages as disjoint finite unions of finite languages and uCont_k(Γ0, …, Γk−1)v languages, and as finite Boolean combinations of finite languages and u(Γ0…Γk−1)+v languages.The Γ_i are nonempty subsets of the alphabet, and u and v are words.Source: §4.4 · p. 31
• (ab)+ and b∗a(a + b)∗ have constant circuit complexity, whereas a+b+ and b∗ab∗a(a + b)∗ have circuit complexity Ω(log n).The latter two complexities are further specified as Θ(n) and Θ(log n), respectively.Source: §4.4 · p. 31
• The FO1[Σ, arb] characterization yields constant-size circuits by reducing formulas to existential quantification over a quantifier-free conjunction.The proof groups numerical predicates to identify positions and uses constant-size circuits for the resulting formulas.Source: §4.4 · pp. 33–34

4.4.1 The Neutral Letter Languages of Constant Circuit Complexity

• For regular neutral-letter languages, constant circuit complexity is equivalent to being idempotent and commutative, a Boolean combination of Γ+ languages, and definable in FO1[Σ].The characterization also includes the stated disjoint-union form.Source: §4.4.1 · p. 35

4.5 From Algebra to Circuit Complexity Lower Bounds

• If a regular language’s syntactic morphism is not in QEJ1, its circuit complexity is Ω(log n).The lower bound follows when the stable semigroup falsifies at least one of the defining identities.Source: §4.5 · p. 35, §4.5.1 · p. 39
• A circuit gives the same acceptance result after letters are rearranged among equivalent positions, provided the set of letters there is unchanged.The proof uses this invariance to contradict the existence of circuits separating constructed word pairs.Source: §4.5 · pp. 36–38
• Falsifying either of two specified identities in the stable semigroup suffices for an Ω(log n) lower bound.The proposition reduces the lower-bound proof to these identity violations.Source: §4.5 · p. 36

4.5.1 Proof of Theorem 4.17

• The proof of the theorem handles the two identity-failure cases separately, each yielding the logarithmic lower bound.One case uses the first proposition point; the other derives a second identity failure before applying its second point.Source: §4.5.1 · p. 39

4.6 From Algebra to Congruence

• For a stamp in QEJ1 with stability index s and stable semigroup size N, u ≈_2sN v implies φ(u) = φ(v).The proposition’s bound depends on both the stability index and the size of the stable semigroup.Source: §4.6 · p. 39
• A regular language with syntactic morphism in QEJ1 is a union of ≈_k classes for some k ≥ 1.The proof applies the proposition with k = 2sN.Source: §4.6 · p. 40
• The proof uses idempotent blocks inserted between letters to relate words with matching residue-class content.The auxiliary lemma establishes that the inserted conjugates are idempotent and preserves the stamp value under the stated conditions.Source: §4.6 · pp. 40, 42, 43

4.6.1 Proof of Proposition 4.24

• In the proposition proof, words agreeing under ≈_2k are split into prefixes and a common suffix shorter than k, reducing the claim to ≈_k-equivalent prefixes.The ≈_k case then follows from the preceding lemma.Source: §4.6.1 · pp. 45–46

5 Decidability of Membership in O(1) Circuit Complexity

• The O(1)-membership problem for NFAs is PSPACE-complete.Source: §5 · p. 46, §5.2 · p. 49

5.1 Upper Bound

• The upper bound decides in polynomial space whether the language’s syntactic morphism satisfies the identities characterizing QEJ1.The proof works with Boolean transition matrices and checks the required stabilizer membership and identity conditions in polynomial space.Source: §5.1 · pp. 46, 48, 49

5.2 Lower Bound

• PSPACE-hardness follows by a logarithmic-space reduction from NFA universality, adding a fresh neutral-letter loop to every state.The constructed language has constant circuit complexity exactly when the original NFA accepts every word.Source: §5.2 · pp. 49–50

6.1 The Pseudovariety QEACom and ≈t k-languages

• QEACom generalizes J1 and includes threshold languages; its regular languages have equivalent descriptions using congruence classes, counting-threshold languages, and one-variable logic.Source: §6.1 · pp. 50–51
• QEACom regular languages have O(log n) circuit upper bounds, but c*cac*bc*c also has O(log n) complexity and is not in QEACom.Source: §6.1 · p. 53

6.1.1 From Logic to Congruence

• For regular languages, one-variable formulas with arbitrary numerical predicates can be replaced by regular numerical predicates, yielding languages that are unions of ≈t k-classes.Source: §6.1.1 · pp. 54–56

6.2 Comparison with Other Input Encodings

• Subset circuits and one-hot circuits with promise are equivalent after scaling input length by alphabet size; thus c(φ(L))(kn)≤f(n) implies c(L)(n)≤f(n).Source: §6.2 · p. 58
• The paper also states that one-hot encoding without promise is not a robust circuit model.Source: §6.2 · pp. 58–59
• Without a promise, the one-hot constant-complexity class is not closed under complement or inverse length-multiplying morphisms, and thus is not an lm-variety.The discussion points to Section 3.3 for further details.Source: §6.2 · p. 59
• K = {01, 10}+ has circuit complexity Ω(log n), because it cannot be represented as the stated disjoint union of finite languages and uCont_k(Γ_0, …, Γ_{k−1})v languages.If all Γ sets are singletons, the number of length-2n words in K is 2^n, contradicting bounded growth; if any Γ has size two, the resulting language contains words at Hamming distance one, unlike K.Source: §6.2 · p. 59
• The morphic image φ({b}+) has constant circuit complexity, whereas φ(α−1({b}+)) = φ(L) has complexity Ω(log n).The constant-size circuit checks that even-length inputs alternate 0 at even positions and 1 at odd positions.Source: §6.2 · p. 59

7 Conclusion

• Constant-complexity regular languages are characterized logically, algebraically, by word congruences, and as finite disjoint unions of specified finite and structured languages.Source: §7 · p. 60
• The neutral-letter class is characterized by idempotence and commutativity, while deciding constant circuit complexity for an NFA is PSPACE-complete.Source: §7 · p. 60
• Rational truth-table reductions preserve circuit-complexity bounds for mild functions, and languages bounded by mild functions form a length-multiplying variety.Source: §7 · p. 60
• Without promise, the one-hot encoding’s constant-complexity regular languages are not a length-multiplying variety.Source: §7 · p. 60
• Understanding the structure of regular languages with circuit complexity in Ω(log n) is left for subsequent work.Source: §7 · p. 60

• Inverse length-multiplying morphisms commute with Boolean operations.Source: A Proofs for Section 3 (Reductions &… · p. 64
• Two-sided quotients commute with Boolean operations.Source: A Proofs for Section 3 (Reductions &… · p. 64
• Inverse length-multiplying morphisms commute with two-sided quotients.Source: A Proofs for Section 3 (Reductions &… · pp. 64–65

Congruence properties

• Words equivalent under the stated circuit relation remain equivalent after adding the same context, and the relations at different indices are compatible.The proofs establish the congruence property and relate the indexed relations when s divides k.Source: B Proofs for Section 4 (The Regular… · pp. 65–66

EJ1 characterization

• A finite semigroup belongs to EJ1 exactly when matching content outside idempotents e and f guarantees π(euf) = π(evf).The proof derives equality under permutations of the intervening word using the stated identities.Source: B Proofs for Section 4 (The Regular… · p. 67

Circuit invariance

• A circuit gives the same acceptance result when letters at equivalent positions are rearranged without changing their set.Positions outside the selected equivalence class remain fixed.Source: B Proofs for Section 4 (The Regular… · p. 68

EACom

• For semigroups in EACom with exponent n, matching truncated content outside e and f implies π(euf) = π(evf).The condition compares content at each threshold t from 0 to n−1 and content at or above n.Source: C Proofs for Section 6 (Discussion) · p. 70

Circuit encodings

• Subset encoding and one-hot encoding with promise are equivalent while preserving the circuit-size function f(n).The one-hot family uses input length kn for words of length n; the converse construction also preserves the number of non-input gates.Source: C Proofs for Section 6 (Discussion) · pp. 71–72