PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy

Takayuki Kuriyama

arXiv:2608.29639v1cs.FLmath.GR

TL;DR

The paper asks how much syntactic information can be compressed while preserving guarded substitution through a given tuple arity. It characterizes the minimum using finite relational morphisms and proves that uniform pseudovariety heights are only 1, 2, or infinity, with the infinite case determined by Synt({ab}).

  • Problem

    The question is how much of a regular language’s syntactic monoid must be retained when only guarded substitution, rather than exact recognition, must be preserved.

    Source: §1.1 · p. 2

  • Method

    The paper derives principal conflicts from SCL geometry and characterizes regular-language compression as least-codomain separation by relational morphisms of the pointed syntactic monoid.

    Source: §1.1 · pp. 2–3, §4 · p. 13, §4.5 · p. 18

  • Results

    Uniform compression heights lie in {1, 2, ∞}, and ch(V) = ∞ exactly when Synt({ab}) belongs to V.

    Source: §9 · p. 40

  • Takeaways & Limitations

    Compression height concerns stabilization of finite compositional separation, not stabilization of concept lattices or quotient complexity.

    Source: §9 · p. 40

    The general structural boundary between pseudovarieties of compression height one and two remains open.

    Source: §7 · p. 33

Abstract

from arXiv · show

Clark's syntactic concept lattice (SCL) records two-sided distributional structure, and Wurm extended it to tuples of arbitrary finite arity. We study \(\operatorname{cmp}_f(L)\), the minimum image size of a finite-monoid observation that preserves guarded tuple substitution through arity \(f\) on the principal layer. For regular languages, we characterize \(\operatorname{cmp}_f(L)\) exactly as the least cardinality of the codomain of an \(f\)-separating relational morphism from the pointed syntactic monoid. Let \(\operatorname{ch}(\mathbf V)\) denote the least arity at which these compression numbers stabilize uniformly over a pseudovariety \(\mathbf V\). Our main result is the following trichotomy of possible uniform heights: \(\operatorname{ch}(\mathbf V)\in\{1,2,\infty\}\), with \(\operatorname{ch}(\mathbf V)=\infty\) if and only if \(\operatorname{Synt}(\{ab\})\in\mathbf V\). Thus no finite uniform compression height \(3,4,\ldots\) occurs. The infinite case is sharp: inside \(\langle\operatorname{Synt}(\{ab\})\rangle\), every boundary \(d\to d+1\) admits unbounded compression gaps, and arbitrary finite strict prefixes of the arity hierarchy are realizable. On the finite side, commutative monoids and bands stabilize at arity one, while every completely regular syntactic monoid stabilizes by arity two; finite group kernels show that the binary bound is sharp. At unary arity, every nonempty finite simple graph is realized by an explicit length-three language, yielding an exact chromatic-number formula and NP-completeness of deciding \(\operatorname{cmp}_1(L)\le 3\) for explicitly listed length-three languages. The structural boundary between compression heights one and two remains open.

1 Introduction

The paper treats finite-monoid compression as a task-relative way to preserve guarded substitution conflicts generated by the principal SCL geometry. Individual languages can have long, sharply increasing arity hierarchies, while uniform pseudovariety heights are restricted to 1, 2, or infinity.

1.1 Finite compositional compression

  • The compression number minimizes a finite compositional observation for guarded substitution, rather than preserving all syntactic information or the full concept lattice.The invariant is task-relative, and its finite semantics generally requires a relational morphism rather than a quotient of the syntactic monoid.Source: §1.1 · pp. 2–3

1.2 Arity hierarchy and main theorem

  • Within ⟨Synt({ab})⟩, every arity boundary can have unbounded compression gaps, and individual languages can realize arbitrary finite strict arity prefixes.Successive ratios in those prefixes can exceed arbitrary prescribed finite thresholds.Source: §1.2 · p. 3
  • Uniform compression heights satisfy ch(V) ∈ {1, 2, ∞}, and ch(V) = ∞ exactly when Synt({ab}) belongs to V.Consequently, no finite uniform heights 3, 4, … occur.Source: §1.2 · p. 3
  • Commutative monoids and bands stabilize at arity one, while completely regular syntactic monoids stabilize by arity two; group kernels make the binary bound sharp.For group kernels, cmp1 = 1 and cmpf = [G : Z(G)] for f ≥ 2.Source: §1.2 · p. 4
  • Every nonempty finite simple graph is realized by a length-three language with cmp1(LG) = χ(G), and deciding cmp1(L) ≤ 3 for explicitly listed length-three languages is NP-complete.The corresponding decision problem for an explicitly given finite pointed syntactic monoid is also NP-complete.Source: §1.2 · p. 4

1.3 Related work and scope of contribution

  • The paper’s contribution is the finite-semigroup characterization and arity theory, not the numerical minimum itself, which also appears as obsf in a companion MCFG manuscript [27].The related-work discussion distinguishes its monoid optimization from compatible-cover methods for incompletely specified machines.Source: §1.3 · pp. 4–5

1.4 Organization

  • The paper proceeds from SCL and algebraic interfaces to arity amplification, completely regular saturation, the global trichotomy, and graph realization with complexity results.It closes with remaining problems.Source: §1.4 · pp. 5–6

2 Syntactic Concept Geometry and Finite-Monoid Compression

The section builds the finite-tuple SCL geometry from word contexts and identifies the principal layer as the relevant domain for guarded substitution. It defines compression through arity f and reduces regular-language SCLs to finite contexts over the syntactic monoid.

2.1 The Clark–Wurm finite-tuple tower

  • For each arity d, tuples are incident to ordered tuple contexts exactly when filling their holes yields a word in L.The resulting closed object sets form Wurm’s SCLd(L), and unary principal concepts identify with the syntactic monoid for regular languages.Source: §2.1 · p. 6

2.2 Principal-intent overlap

  • Principal-overlap edges connect distinct tuple concepts whose accepting-context intents intersect, the conflicts that finite-monoid safety must separate.The safety condition forbids equal componentwise monoid types for tuples generating distinct adjacent principal concepts.Source: §2.2 · p. 7
  • The principal layer is the substitution layer because words and tuples inserted into contexts map to principal concepts, not arbitrary closed aggregates.The paper limits its canonicity claim to this guarded substitution task.Source: §2.2 · p. 7

2.3 Compression number

  • The compression number cmpf(L) is the minimum image size of a finite-monoid homomorphism safe through arity f.The companion MCFG notation obsf agrees with cmpf when applied to the same language, despite using permutation sectors [27].Source: §2.3 · pp. 7–8
  • For every d, ⌈χ(Ωd(L))^(1/d)⌉ ≤ cmpd(L), so infinite chromatic number of the principal overlap graph rules out every finite witness.This lower bound follows by coloring concepts using componentwise monoid values realized by generating tuples.Source: §2.3 · p. 8

2.4 Finite SCL reduction for regular languages

  • For regular L, the d-ary SCL is isomorphic to a finite concept lattice built from the syntactic monoid and P = η(L).Its incidence test is q0t1q1 ··· tdqd ∈ P; the syntactic maps preserve incidence in both directions, so duplicate rows and columns are the only information lost.Source: §2.4 · pp. 8–9

3 Word-Level Conflict and Compositional Compression

The section translates guarded substitution safety into explicit conflict constraints on words, then into algebraic compression for regular languages. Unary safety is compositional graph coloring; higher arities impose wider separation clauses.

3.1 The arity-one conflict graph

  • At arity one, cmp1 is the minimum size of a monoid-compatible coloring of the contextual-conflict graph, while ordinary coloring gives a lower bound.The difference between the two quantities is the price of requiring compositionality.Source: §3.1 · p. 10
  • For L = {a, a3}, the unary conflict graph has chromatic number 2 but cmp1(L) = 3, exhibiting a strict cost of compositionality.A two-element monoid image cannot separate both conflict edges, whereas a generator of C3 does.Source: §3.1 · pp. 10–11

3.2 Regular languages: from coloring to syntactic semantics

  • The finite conflict graph of a regular language is a blow-up of its syntactic conflict graph, preserving chromatic number.Words in one syntactic class are nonadjacent, and adjacency between distinct classes is uniform across representatives.Source: §3.2 · p. 11
  • For regular languages, χ(ΓL) ≤ cmp1(L) ≤ qcmp1(L) ≤ |TL|, and all four resources in the conflict-to-syntax ladder can separate strictly.For Kn = {an, an+2}, every f ≥ 1 has χ(ΓKn) = 2 < 3 = cmpf(Kn) < n + 2 = qcmpf(Kn) < n + 4 = |TKn|; the relational–quotient gap grows as n − 1.Source: §3.2 · pp. 11–12
  • Relational compression can retain distinctions inside a dead syntactic class that every functional quotient loses.For the Kn example, the canonical relation assigns all three C3 values to the common dead class, retaining residue information.Source: §3.2 · p. 12

3.3 Higher arity as a compositional separation system

  • At arity d > 1, each unsafe tuple pair imposes a disjunctive separation clause across its d coordinates, so higher arity generalizes graph coloring to a compositional separation system.The finite-index congruence formulation gives this constraint system an exact algebraic form.Source: §3.3 · pp. 12–13

4 Algebraic Characterization of Conflict Resolution

The section recasts guarded substitution safety as algebraic separation: first by finite-index congruences, then, for regular languages, by relational morphisms of the pointed syntactic monoid. This yields an exact minimum-codomain characterization and shows that commutative syntax collapses the arity hierarchy at one.

4.1 Free-monoid separation clauses

  • An f-separating finite-index congruence separates at least one coordinate of every unsafe tuple pair of arity at most f.For unary arity, each constraint is simply a required separation.Source: §4.1 · p. 13, §4.4 · p. 17

4.2 Finite syntactic profiles for regular languages

  • For regular L, tuple contexts have finite profiles over its pointed syntactic monoid, and these profiles exactly transport semantic unsafe pairs.The pointed monoid is (T, P), where T is the syntactic monoid and P is the image of L.Source: §4.2 · pp. 13–14

4.3 Canonical relational morphism of a compression map

  • The Safety Interface Theorem equates principal-SCL, context, unsafe-pair, congruence, and canonical relational-morphism formulations of the same safety predicate.The theorem concerns the canonical relation induced by a fixed compression map; it does not identify every relational morphism with such a canonical relation.Source: §4.3 · pp. 15–16

4.4 Free-monoid congruence characterization

  • For every language, cmp_f(L) is the minimum index of a finite f-separating monoid congruence, giving the nondecreasing chain cmp_1(L) ≤ cmp_2(L) ≤ ··· ≤ |T_L| for regular L.Higher arity imposes successively stronger separation constraints, without generally requiring exact syntactic recognition.Source: §4.4 · pp. 16–17

4.5 Relational-morphism characterization

  • For regular L, cmp_f(L) equals the least codomain size of a finite f-separating relational morphism from its pointed syntactic monoid.A free-monoid selector turns any such relation into a functional witness of no larger image size; the full compression sequence is invariant under pointed-monoid isomorphism.Source: §4.5 · pp. 17–18

4.6 A core finite-side bound: commutative collapse

  • If L has a commutative syntactic monoid, unary substitutability for a compression map is equivalent to substitutability at every finite arity, so cmp_1(L) = cmp_2(L) = ···.Commutativity lets tuple fillings be compared through their concatenated products and unary contexts.Source: §4.6 · pp. 18–19

5 Arity Amplification inside Vab

Inside V_ab, letter-distinct finite languages provide amplifiers whose compression can stay bounded through one arity while becoming arbitrarily large at the next. Gluing these amplifiers realizes arbitrary finite strict prefixes, while the resulting uniform height for V_ab is infinite.

5 Arity Amplification inside Vab

  • For every d ≥ 1, languages in V_ab can have bounded cmp_d but arbitrarily large cmp_(d+1), with witnesses using words of length at most 2d + 1.The construction uses finite letter-distinct languages recognized by monoids in V_ab.Source: §5 · pp. 19, 21

5.1 Finite-prefix universality inside Vab

  • For every finite m and prescribed positive thresholds λ_f, one finite letter-distinct language in V_ab has cmp_(f+1)(L) > λ_f cmp_f(L) at every boundary f < m.Triangular gluing combines boundary amplifiers; the resulting language has words of length at most 2m − 1.Source: §5.1 · pp. 22–23

5.2 SCL compression height

  • The compression sequence of each fixed regular language stabilizes, but no single stabilization arity works uniformly over V_ab, so ch(V_ab) = ∞.The infinite height describes failure of a uniform bound across the class, not divergence for an individual language.Source: §5.2 · p. 23

6 Completely Regular Monoids Saturate at Arity Two

This section shows that for completely regular finite syntactic monoids, binary safety of a compatible tolerance extends to every finite tuple arity, yielding compression-number stabilization from arity two onward. It establishes a uniform height bound of two for all finite completely regular monoids.

6.1 Local rigidity inside an accepting completely simple component

  • In each accepting completely simple component, 2-safety forces related elements into the same H-class, differing by an element of a central normal subgroup Nβ.The local kernel Nβ is normal, and the resulting local rigidity applies even though the tolerance need not be transitive.Source: §6.1 · pp. 26–27

6.2 Uniform central defects

  • Related pairs acting on an accepting component have a unique central defect, and the defect map is a monoid homomorphism that factors through tuple contexts.For a related pair in the component, the unique defect describes its central translation; contextual factorization leaves only coordinate defects because fixed pairs have defect 1.Source: §6.2 · pp. 27–28

6.3 Binary compression of an arbitrary tuple

  • For coordinatewise related tuples sharing an accepting context, 2-safety forces their ordered coordinate products to be equal.Support bookkeeping places context fillings in the same completely simple component when their coordinate support products agree.Source: §6.3 · p. 29

6 Completely Regular Monoids Saturate at Arity Two

  • Every 2-safe compatible tolerance on a completely regular finite syntactic pointed monoid is safe at every finite tuple arity.This holds without assuming the tolerance is transitive; by the relational-morphism dictionary, f-separation corresponds exactly to f-safety.Source: §6 · p. 24, §6.3 · p. 30

6.3 Binary compression of an arbitrary tuple

  • For the pseudovariety CR of all finite completely regular monoids, the uniform compression height satisfies ch(CR) ≤ 2.Source: §6.3 · p. 31
  • The proof works beyond orthogroups by using central translation defects on a lower accepting completely simple component to synchronize tuple contexts.Product compression first converts shared higher-arity acceptance into equality of coordinate products; the defect calculus then handles inserted fixed factors.Source: §6.3 · pp. 30–31

7 Global Compression-Height Trichotomy and Sharp Regimes

Uniform compression heights are only 1, 2, or infinity, with infinity characterized by membership of Mab; the section also establishes sharp finite regimes and identifies an unresolved boundary between heights one and two.

7 Global Compression-Height Trichotomy and Sharp Regimes

  • ch(V) is 1, 2, or infinity, and it is infinite exactly when Mab belongs to V; otherwise V lies in Com or CR and has height 1 or at most 2.The structural dichotomy follows because every finite non-completely-regular monoid has U as a divisor, while a noncommutative monoid together with U yields Mab as a divisor of U^2 × M.Source: §7 · pp. 31–33

7.1 Group syntactic monoids: relational compressions collapse to quotients

  • For a regular language with finite group syntactic monoid G, every finite-monoid compression can be replaced by a quotient-group witness of no greater size.The quotient-collapse result identifies relational compression and quotient compression at every arity.Source: §7.1 · p. 33

7.2 A second height-one mechanism: bands

  • Every unary-separating relational morphism from a finite band is separating at every finite arity, so cmp1(L) = cmp2(L) = ···.The proof uses absorption across the semilattice decomposition into rectangular bands.Source: §7.2 · p. 34

7.3 Kernel group languages: arity two detects inner conjugation

  • cmp1(Kη) = 1, while cmpf(Kη) = [G : Z(G)] for f ≥ 2; consequently, CR pseudovarieties containing a nonabelian finite group have height 2.The classification of height-one pseudovarieties within CR remains open when all their group members are abelian.Source: §7.3 · pp. 34–35

7.4 Height sharpness and classical benchmarks

  • The band pseudovariety has height 1, whereas the completely regular pseudovariety has height exactly 2, witnessed by the kernel language for S3 with cmp1 = 1 and cmpf = 6 for f ≥ 2.The nontrivial center-index jump makes the completely regular binary bound sharp.Source: §7.4 · p. 35

7.5 Benchmark pseudovarieties and minimal obstructions

  • The benchmark values are 1 for Com and B, 2 for G and CR, and infinity for A, J, R, and L; all three heights occur on the minimal noncommutative frontier described in the paper.Mab belongs to A and J, and J is contained in R and L.Source: §7.5 · pp. 35–36

8 Graph Realization and Computational Complexity

Every nonempty finite simple graph is realized as the unary conflict geometry of an explicit length-three language, yielding exact chromatic-number and NP-completeness results. The section also establishes NP-completeness for the corresponding pointed-monoid optimization problem.

8.1 Graph-language construction

  • The construction assigns two edge words and one private word per vertex, all of length three, using distinct marker terminals.Consequently, |LG| = 2|E| + |V|.Source: §8.1 · p. 36

8.2 Classification of unsafe factors

  • The unsafe-pair graph of LG has edges exactly between vertex terminals xu and xv corresponding to edges of G; all other terminals are isolated.Thus the designated terminals induce a copy of G in the contextual-conflict graph and unary principal-overlap graph.Source: §8.2 · p. 37

8.3 Exact realization of chromatic number

  • For every nonempty finite simple graph G, the constructed length-three language LG satisfies cmp1(LG) = χ(G).The construction is polynomial time, uses a variable alphabet, and has |LG| = 2|E| + |V|.Source: §8 · p. 36, §8.3 · p. 38

8.4 The finite-language decision problem

  • When the alphabet is part of the input, deciding cmp1(L) ≤ 3 for explicitly listed length-three languages is NP-complete.Membership uses a constant-size monoid certificate at the fixed threshold; hardness follows from graph 3-colorability.Source: §8.4 · p. 39

8.5 Complexity from an explicit pointed monoid

  • Pointed-Obs1 is NP-complete, with NP-hardness already at threshold k = 3 for syntactic pointed monoids of length-three languages.The graph reduction computes the pointed syntactic monoid in polynomial time and preserves the optimum: its least unary-separating relational-morphism codomain size is χ(G).Source: §8.5 · p. 40

9 Discussion and Open Problems

The discussion contrasts arbitrarily rich arity hierarchies for individual languages with a three-valued uniform-height spectrum over pseudovarieties. It identifies an unresolved height-one boundary and open complexity questions, alongside the paper’s declarations.

9 Discussion and Open Problems

  • Uniform heights satisfy ch(V) ∈ {1, 2, ∞}, with ch(V) = ∞ exactly when Synt({ab}) belongs to V.Within the generated pseudovariety, individual languages can still have arbitrary finite strict arity prefixes and unbounded successive gaps.Source: §9 · p. 40
  • The trichotomy concerns stabilization of finite compositional separation, not stabilization of concept lattices or quotient complexity.Nonabelian group kernels can have growing principal tuple geometry while their compression optimum stabilizes at arity two.Source: §9 · p. 40
  • Whether every completely regular pseudovariety with only abelian groups has height one remains open.The paper proposes identity-adjoined completely simple Rees matrix monoids over finite abelian groups as a test family.Source: §9 · p. 41

Statements and Declarations

  • The author reports no funding, competing interests, or generated or analyzed datasets, and reports using ChatGPT for literature searching, proof auditing, organization, and language editing.The author states responsibility for the mathematical statements, proofs, citations, and final manuscript.Source: Statements and Declarations · p. 41
Loading 2608.29639v1…