Metraipolis › archive › dc_7b413893f505
Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy — arXiv:2608.29639
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.29639
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T10:07:29.887Z
- SHA-256 of the archived text
07990ebf9f3f1521d50c3290402bac21e49e6f44e24dbf3fa446d53017f7d46b- Stable URL of this page
https://metraipolis.com/documento/dc_7b413893f505
How to cite
Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy — arXiv:2608.29639 — arXiv (en), https://arxiv.org/abs/2608.29639 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b413893f505 (Metraipolis archive dc_7b413893f505, sha256 07990ebf9f3f1521d50c3290402bac21e49e6f44e24dbf3fa446d53017f7d46b)
BibTeX
@misc{dc7b413893f505,
title = {Finite-Monoid Compression in Syntactic Concept Lattices: Arity Hierarchies and a Pseudovariety Trichotomy — arXiv:2608.29639},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.29639},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b413893f505; sha256 07990ebf9f3f1521d50c3290402bac21e49e6f44e24dbf3fa446d53017f7d46b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.29639. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL) ; Group Theory (math.GR).
Pagina del lavoro: https://arxiv.org/abs/2608.29639 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T10:02:33.389Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).