CS Paper Radar

Irreducibility of Endomorphisms of Finitely Generated Free Semigroups

Paul C. Bell, Eva Foster, Daniel Reidenbach

cs.FL math.GR ·submitted 2026-10-05 17:37 UTC · v1
published

Abstract

We introduce and investigate the irreducibility of endomorphisms of finitely generated free semigroups, i.e., we investigate when an endomorphism $φ: Σ^+ -> Σ^+$, where $Σ$ is any alphabet, can be nontrivially expressed as a composition $φ= ψ_2 \circ ψ_1$ of endomorphisms $ψ_1, ψ_2: Σ^+ -> Σ^+$. We, hence, study a notion of primality in the endomorphism monoid of the free semigroup---a natural and fundamental concept in this algebraic structure. We establish that irreducibility is a nontrivial property for the class of so-called rank-preserving endomorphisms, and we provide a characteristic condition separating the reducible and irreducible endomorphisms. We also characterise when an endomorphism is a factor of another endomorphism, analyse the non-uniqueness of factorisations of a rank-preserving endomorphism into its irreducible components, and investigate the use of incidence matrices to give insights into the (ir-)reducibility of rank-preserving endomorphisms.

Comment
In Proceedings AFL 2026, arXiv:2608.23071
Journal ref
EPTCS 451, 2026, pp. 60-74
DOI
10.4204/EPTCS.451.5

Closest papers

Nearest neighbours by meaning across the whole index.

Proving at Scale for Universal Algebra

cs.LO math.GR ·2026-10-01 ·João Araújo, Jan Hůla, Mikoláš Janota, Edmond W. H. Lee, Bartosz Naskręcki
similarity 0.60
Abstract

We introduce SemiBase, a project that computes and formally certifies finite identity bases for small semigroups. Deciding finite basability is undecidable for finite algebras and remains open for finite semigroups. The task requires a proof that a candidate basis is complete, or a proof that none exists, rather than a single first-order validity query. LLM-guided agents search for these proofs; a referee agent rebuilds them from source, and the Lean kernel checks the resulting corpus in a final audit. Humans choose targets and approve final outcomes. We certify every semigroup of order at most 6: all 1309 semigroups of order at most 5 and all 15973 of order 6, including proofs that the four known nonfinitely based semigroups have no finite basis. The bases for order 6 define 505 distinct varieties, whose inclusion order Vampire determines except for four pairs. The resulting catalogue is a machine-checked account of results scattered across the literature and a tested foundation for order 7.

0.25

Conjugacy languages in free inverse monoids

cs.FL math.GR ·2026-08-11 ·André Carvalho, Ana-Catarina C. Monteiro
similarity 0.60
Abstract · preliminary version, 24 pages

We initiate the study of conjugacy languages in free inverse monoids. Motivated by the notion of conjugacy languages in groups and the study of conjugacy in semigroups, we introduce the language of shortest representatives of conjugacy classes and study it for free inverse monoids of rank at least $2$ under the natural notion of conjugacy. We show that, contrary to the free group case, where this language is regular, in a free inverse monoid it is neither context-free nor co-context-free. In the monogenic case, this language is context-free. We show that this non-context-freeness comes from elements with nontrivial conjugacy classes. We define an equivalence relation as follows: all elements with a nontrivial conjugacy class are related and elements with trivial conjugacy class are only related to themselves. We call this relation $\mathrm{UConj}$. We show that the language consisting of geodesics representing elements whose conjugacy class is trivial is context-free by providing an explicit context-free grammar generating it. For groups, we show that the language of minimal representatives of $\mathrm{UConj}$ classes is regular if the group is hyperbolic and for right-angled Artin groups with the standard generating set, it is piecewise testable. For virtually abelian groups, we show that there is a generating set for which this language is piecewise excluding and exhibit an example of a virtually abelian group admitting a generating set for which this language is not regular.

0.10

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse

cs.LO math.LO ·2026-10-29 ·Kirill Osipov
theory similarity 0.58
Abstract

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 1$, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit $G^{[t]}(0)$ has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive $G$. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and $G$ has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.

0.23

Graded Intersection Types

cs.LO cs.PL ·2026-11-12 ·Rémy Cerda, Ugo Dal Lago
similarity 0.57
Abstract

We introduce graded intersection types, in which arrow domains are multisets of types with coefficients in a semiring. Boolean and natural number grades recover idempotent and non-idempotent intersection types. We give algebraic conditions on the semiring for subject reduction and expansion in finite systems and in locally finite systems with guarded infinite types. We construct a lifting to multisets of grades corresponding, in this general setting, to lifting the idempotent system to the non-idempotent one. We recall the main existing operational characterisations from the literature, and show some general extensions.

0.33

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

cs.FL cs.LG ·2026-09-03 ·Takayuki Kuriyama
similarity 0.55
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

Solving polynomial equations over partial discrete dynamical systems

cs.DM ·2026-09-30 ·Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
similarity 0.54
Abstract

The analysis of observable phenomena (for instance, in biology or physics) allows the detection of dynamical behaviours. If the conditions are ideal and the number of observations is sufficient, we can represent these phenomena by a dynamical system, also called a functional digraph, that is to say a graph where each node has out-degree exactly one. Up to isomorphism, these dynamical systems, equipped with disjoint union as addition and direct product as multiplication, form a commutative semiring. Several previous studies on this semiring have aimed to establish algebraic properties (primality, injectivity) or complexity results (division, factorisation). However, no work has yet been conducted on graphs derived from imperfect observations that result in missing transitions or nodes, in other words, in cases where each node in the graph has an out-degree of at most one. In this case, we say that the system is partial. In this paper, we show that partial dynamical systems, up to isomorphism and equipped with the same addition and multiplication, still form a commutative semiring. We then characterise the prime elements of this semiring, which differ from those of the semiring of dynamical systems. Finally, we highlight two properties shared by both semirings. First, injective univariate polynomials admit the same characterisation in both. Second, division can be computed in polynomial time for partial dynamical systems if and only if it can be for dynamical systems.

0.34

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

cs.FL math.GR ·2026-08-30 ·Takayuki Kuriyama
similarity 0.54
Abstract · 43 pages, 2 tables

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.

0.31

Length Bounds for Irreducible Cyclic MDS Codes

cs.IT ·2026-10-20 ·Guanghui Zhang
theoryhot direction similarity 0.54
Abstract · 35 pages

We prove the MDS length bound for nontrivial irreducible cyclic codes of every composite length. The classical trace realization turns the MDS property into independence of elements of a multiplicative subgroup. Every nonidentity subgroup must have the full extension degree. This restriction yields length congruences, and the Frobenius-orbit description of the coefficient field gives an exact descent obstruction. A cyclotomic argument reduces each fixed dimension to finitely many parameters. For dimensions at most thirty, established geometric bounds reduce the alphabet to a small finite range; the remaining twelve parameter triples are excluded by explicit products of at most three determinant factors and a low-degree multiplier argument. An independent argument proves the composite-length theorem in arbitrary dimension. The standardness conclusion is stated separately as a conditional consequence of the classification statement of Feng, Hollmann, Li, and Xiang; the correct extension-field reduction retains a semilinear quotient. The general prime-length problem is not settled here. Neither length proof uses the automorphism classification or the recent odd-characteristic range announced by Fan.

0.34