CS Paper Radar

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

Takayuki Kuriyama

cs.FL math.GR ·submitted 2026-08-30 08:02 UTC · v1

Abstract

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.

Comment
43 pages, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Guillotine and Tiling Cofiniteness in Unary Picture Languages

cs.FL ·2026-08-25 ·Pierluigi San Pietro, Stefano Crespi Reghizzi, Antonio Restivo
publishedtheory similarity 0.64
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Motivated by the study of closure operations on picture languages, we ask when a set of unary tiles can generate all sufficiently large pictures either via repeated horizontal and vertical concatenations or via tiling operations. In one dimension, the lengths of words in the concatenation closure of a unary language form an additive subsemigroup of positive natural numbers; hence, they are finitely generated. Cofiniteness is characterized by the gcd of these generators being one. Since ordinary cofiniteness in two dimensions is too restrictive and essentially reduces to degenerate one-dimensional conditions on strips, we introduce and study asymptotic cofiniteness: all sufficiently large rectangular pictures are generated. A direct extension of the one-dimensional criterion, requiring the gcd of the tile heights and of the tile widths to be one, is not sufficient, because local congruence obstructions may persist in two dimensions. We give an exact arithmetic characterization of asymptotic cofiniteness for arbitrary, possibly infinite, sets of unary rectangular tiles. The characterization is the same for the guillotine closure, obtained by horizontal and vertical concatenation, and for the full tiling closure. For finite tile sets, the proof combines semigroup arguments and an explicit least-common-multiple stacking construction for sufficiency, while necessity is obtained by a roots-of-unity argument applying also to nonsliceable tilings. The extension to infinite tile sets follows from the finite-basis theorem for Klarner systems.

0.36

A generalized monoid of infinite words: asymptotic prefix-suffix quotients and algebraic structure

cs.FL math.GR ·2026-08-20 ·A. Alvarez Cruz, E. A. Alvarez Gutierrez
similarity 0.63
Abstract

A generalized monoid of words tilde{Sigma}* is constructed as the quotient of moderate nets of finite words by an asymptotic equivalence relation based on a bidirectional prefix-suffix metric. The main algebraic result is that this quotient is a monoid containing Sigma* faithfully, with a reversal involution, a natural divisibility preorder, failure of cancellation, and nontrivial idempotents. The construction is designed so that any functional depending only on a logarithmic prefix descends to the quotient, yielding a well-defined action of logarithmic-prefix functionals. Finite scalar values arise only after applying an additional renormalization functional, which depends on the chosen mould and window. With respect to the fixed truncation injection, the monoid strictly enlarges the classical set Sigma^{infty}: an explicit oscillating net is exhibited that has no limit in the Cantor space but defines a genuine element of tilde{Sigma}* not coming from a finite or right-infinite word under that injection.

0.50

When Matchgate Base Collapse Fails: A Qutrit Trichotomy and Unbounded Exact Width

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng
similarity 0.61
Abstract

Holographic algorithms solve planar counting problems by encoding each value of a finite domain into several Boolean matchgate wires. Base collapse asks whether every exact representation can be compressed to a number of wires per edge bounded only by the domain size. Chen (STOC 2016) and Xia (STOC 2016) established broad positive collapse theorems under full-rank and related structural hypotheses. Together, these works left open whether a domain-only collapse bound survives when several locally deficient signatures must share one encoding. We resolve this open problem negatively, already on a three-state (qutrit) domain. For every $a\ge4$, we construct a five-label integer-valued qutrit language of maximum arity $a$ with an exact rational matchgate presentation, yet every exactly equivalent label-preserving presentation requires common width $Ω(2^{a/2}/a)$, even if its domain, base, tensors, and complex weights may all change. The construction avoids the usual local degeneracies, so the obstruction is genuinely simultaneous. Algebraic geometry then drives an exhaustive trichotomy explaining the boundary of collapse: the gadget closure either separates into rays, is Gaussian-mobile and collapses to width at most three, or is confined to a rigid plane-plus-ray flag containing our unbounded family. Pure-spinor geometry forces compression in the mobile case, while dimension bounds for matchgate varieties and Zariski avoidance place exact integer data outside every low-width algebraic image. Thus one geometric framework explains both why collapse occurs and why it can fail without bound.

0.19

Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation

cs.FL cs.LG ·2026-09-03 ·Takayuki Kuriyama
similarity 0.61
Abstract · 47 pages; reproducible verification code and a machine-readable certificate for the 36-element witness are available via the fixed GitHub sn…

Let $L\subseteqΣ^*$ and fix a morphism $h:Σ^*\to M$ into a finite monoid. We study exact factorization and canonical presentation in the relative syntactic congruence $θ_{L,h}:=\equiv_L\cap\ker h$. We separate unique factorization from finite direct presentation. An exhaustively computer-checked $36$-element quotient has a unique exact prime factorization for every live non-unit class, yet its valid prime-return rules contain an infinite family, so unique factorization does not imply the finite relative presentation property (FRP), even for a finite quotient. We lift the same defect to a nonregular context-free language with an infinite relative quotient and finite prime spectrum. To isolate the obstruction, we introduce the finite-state relative presentation property (FSRP), in which canonical valid right-hand-side languages are represented by finite residual controllers, and prove $\mathrm{FRP}\subsetneq\mathrm{FSRP}$. We then introduce prime-target left-division determinism (PTLD), which implies unique exact factorization, tail exactness, tail determinism, and a quadratic bound on valid rules. A nonregular deterministic context-free example with a finite group observer satisfies PTLD while lying outside every fixed $(k,\ell)$-substitutable class. Finally, for fixed $h$ we give a strong positive-data learner for the canonical PTLD presentation with polynomial-time hypothesis updates and a finite characteristic sample, together with a limit reconstruction of the canonical FSRP controller from weakly behaviorally correct CFG-valued learners.

0.30

Unary Functions, Automorphisms, and Unlabeled First-Order Model Counting

cs.LO cs.DM ·2026-08-31 ·Ondřej Kuželka
theory similarity 0.60
Abstract · fixed typos, 61 pages

Every fixed first-order sentence $\varphi$ determines an enumerative sequence $n\mapsto \mathrm{FOMC}(\varphi,n)$, counting its models on the labeled domain $[n]$. We study the complexity of these sequences when logical specifications may use genuine unary function symbols and hence nested terms such as $x,f(x),f^2(x),\ldots$. We prove that, for every fixed sentence $\varphi\in \mathrm{C}^1_{=}[f]$ with one unary function and an arbitrary finite relational vocabulary, $\mathrm{FOMC}(\varphi,n)$ is computable in time polynomial in $n$. By contrast, either a second variable or a second unary function yields hardness: there is a fixed sentence in $\mathrm{FO}^2_{=}[f]$ whose model-counting function is $\#\mathrm{P}_1$-complete, and there is a fixed constant-free universal sentence in $\mathrm{FO}^1_{=}[f,g]$, using only unary predicates besides $f$ and $g$, with the same property. We also relate labeled and unlabeled enumeration exactly. For every relational sentence $\varphi$, we construct an extension $\varphi_{\mathrm{aut}}$ in which a unary function records an automorphism and $\mathrm{FOMC}(\varphi_{\mathrm{aut}},n)=n! \cdot \mathrm{UFOMC}(\varphi,n)$, where $\mathrm{UFOMC}(\varphi,n)$ counts the $n$-element models of $\varphi$ up to isomorphism. This gives a one-query exact reduction from unlabeled to labeled model counting at the same domain size. If $\varphi$ belongs to $\mathrm{FO}^k_{=}$, respectively $\mathrm{C}^k$, and its relational vocabulary has maximum arity $r$, eliminating the auxiliary function yields a single-query reduction to labeled model counting in $\mathrm{FO}^{\max\{k,r+1\}}_{=}$, respectively $\mathrm{C}^{\max\{k,r+1\}}$.

0.19

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.60
Abstract

We consider some operations on finite automata graphs, in particular various product, union and merge operations, and investigate how they relate to the parameter~$\mathrm{rt}$, the \emph{length of a shortest synchronizing word}. We derive some lower and upper bounds for the operations that we study. We also examine several classes of automata (for instance, partially ordered, commutative or idempotent automata) that are preserved under these operations and show in which way the parameter $\mathrm{rt}$ behaves in these automata classes. Also, we consider automata classes that can be constructed by combining automata from better known classes; in particular, these new classes of automata will also satisfy the bound of the famous Černý conjecture. This also motivates us to study even more closure properties. In particular, we show that certain automata classes related to synchronization form pseudo-varieties. We also commence a similar study concerning the length of shortest homing sequences of Mealy automata.

0.13

Finite Dependence and Invariance Hierarchies for Finitely Supported Structures

cs.LO math.CTmath.LO ·2026-09-14 ·Gabriel Ciobanu
similarity 0.59
Abstract · 44 pages, 2 tables, no figures. Unified synthesis of finite-dependence profiles, invariance hierarchies, freshness, context composition, orb…

Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

0.49

Algebraic Decomposition Theory for Transformer Length Generalization

cs.FL cs.AI ·2026-08-13 ·Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac, Andreas Krebs +3 more
similarity 0.59
Abstract · 54 pages, 12 figures

Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.

0.43