Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy
Abstract
Clark's syntactic concept lattice (SCL) records two-sided distributional structure, and Wurm extended it to tuples of arbitrary finite arity. We study cmpf(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 cmpf(L) exactly as the least cardinality of the codomain of an f-separating relational morphism from the pointed syntactic monoid. Let ch(V) denote the least arity at which these compression numbers stabilize uniformly over a pseudovariety V. Our main result is the following trichotomy of possible uniform heights: ch(V)∈{1,2,∞}, with ch(V)=∞ if and only if Synt({ab})∈V. Thus no finite uniform compression height 3,4,… occurs. The infinite case is sharp: inside ⟨Synt({ab})⟩, every boundary d→ 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 cmp1(L)≤ 3 for explicitly listed length-three languages. The structural boundary between compression heights one and two remains open.
Related
- A cardinal trichotomy for topological equivalence classes of countable trees
- Classification of bipartite observables II: NIP observables and the Todorcevic trichotomy
- Non-Wellfounded and Cyclic Proofs for LTL: A Syntactic Correspondence with Linear Nested Sequents
- Generalized Frobenius Structures on Hurwitz Spaces, Their Open Extensions and Associated Principal Hierarchies
- Elliptic orbifold lines and integrable hierarchies
BibTeX
@misc{kuriyama2026finitemonoid,
title = {{Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy}},
author = {Takayuki Kuriyama},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29639},
eprint = {2608.29639},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29639},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy
AU - Takayuki Kuriyama
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29639
UR - https://arxiv.org/abs/2608.29639
AB - Clark's syntactic concept lattice (SCL) records two-sided distributional structure, and Wurm extended it to tuples of arbitrary finite arity. We study 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 cmp_f(L) exactly as the least cardinality of the codomain of an f-separating relational morphism from the pointed syntactic monoid. Let ch(V) denote the least arity at which these compression numbers stabilize uniformly over a pseudovariety V. Our main result is the following trichotomy of possible uniform heights: ch(V)∈{1,2,∞}, with ch(V)=∞ if and only if Synt({ab})∈V. Thus no finite uniform compression height 3,4,… occurs. The infinite case is sharp: inside ⟨Synt({ab})⟩, every boundary d→ 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 cmp_1(L)≤ 3 for explicitly listed length-three languages. The structural boundary between compression heights one and two remains open.
ER -