CS Paper Radar

Testing epimorphism onto the bicyclic monoid is $\mathsf{NP}$-complete

Luka Carroll, Murray Elder

cs.LO math.GR ·submitted 2026-10-06 11:49 UTC · v2
theoryunusual

Abstract

We prove that deciding whether there is a surjective homomorphism from an arbitrary finitely presented inverse monoid onto the bicyclic monoid is $\mathsf{NP}$-complete. As part of the proof, we show that an extension of existential Presburger arithmetic which involves greatest common divisors on $n$ arguments is in $\mathsf{NP}$, extending a recent result of Défossez, Haase, Mansutti, and Pérez (SODA 2024).

Comment
17 pages, 1 figure. Comment about OpenAI result added

Closest papers

Nearest neighbours by meaning across the whole index.

Irreducibility of Endomorphisms of Finitely Generated Free Semigroups

cs.FL math.GR ·2026-10-05 ·Paul C. Bell, Eva Foster, Daniel Reidenbach
published similarity 0.53
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

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.

0.37

Fast factorization in diagram monoids

cs.DS math.RAmath.CO ·2026-09-25 ·Matthias Fresacher, Willow Stewart, Daniel Tubbenhauer
similarity 0.52
Abstract · 39 pages, many figures, comments welcome

We give explicit algorithms that factor elements of the standard diagram monoids into their usual generators. These algorithms generalize sorting from permutations to partial matchings and set partitions. In every case the worst-case complexity is $n^2$, which is optimal for algorithms that explicitly list the factors. We also determine the average complexity of our algorithms.

0.30

Algebraic Characterizations for Minors of Finite Graphs via Flow Transformation Monoid Division and Embedding

cs.DM cs.FL ·2026-08-25 ·Amena Assem, Hanna Derets, Chrystopher L. Nehaniv
publishedtheory similarity 0.51
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We prove three theorems on the flow monoids of finite graphs. First, we show that a non-empty finite graph G = (V, E) is connected if and only if its flow monoid contains a constant map on V, equivalently, if and only if it contains all constant maps on V. Second, we give a new characterization of graph minors in terms of division of flow transformation monoids, together with an algebraic crossing condition that detects edges between the vertex sets being contracted. Third, we strengthen this to an embedded-copy theorem: a graph M is a minor of G if and only if, subject to analogous crossing conditions, the flow transformation monoid of M is realized as the induced action of a subsemigroup of the ambient flow monoid of G, this subsemigroup being a monoid with a local idempotent identity.

0.50

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

cs.FL math.GR ·2026-08-30 ·Takayuki Kuriyama
similarity 0.51
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

On Positive Computation

cs.CC cs.LO ·2026-11-06 ·Eduardo Skapinakis
similarity 0.50
Abstract

We introduce new notions of reducibility for monotone classes and show that a monotone version of Circuit Satisfiability and the Hamiltonian Cycle Problem are complete for $mNP$, even under positive reductions (which are not the same as monotone reductions). If this holds for all (monotone) $mNP$-complete problems - that they are also so complete for $mNP$ -, then $P\neq NP$. We introduce positive models of relativized computation and show that the separation $posP\subsetneq mNP$ does not relativize, even when oracles are restricted to monotone sets. Yet, there is a (weak) diagonalization proof that $posP\subsetneq mNP$.

0.23

Algorithms for Finite Group Epimorphism Testing

cs.DS cs.CCmath.GR ·2026-09-07 ·Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
top venue similarity 0.50
Abstract · 19 pages, A preliminary version of this article appeared in the proceedings of the 53rd EATCS International Colloquium on Automata, Language…

The Group Epimorphism Problem (GpEpi) asks, given two finite groups $G_1$ and $G_2$, whether there exists a surjective group homomorphism, or epimorphism, from $G_1$ to $G_2$. When the input groups are given by their multiplication (Cayley) tables, the problem admits a quasipolynomial-time algorithm in general, but little is known about its complexity for structured classes of finite groups. In this paper, we study the computational complexity of GpEpi for several well-studied classes of finite groups. Our main results are polynomial-time epimorphism tests for several classes of groups for which polynomial-time isomorphism testing was previously known: Groups with Abelian normal Hall subgroups with cyclic complement; Groups with (product of) elementary Abelian normal Hall subgroup with elementary Abelian complement; and Groups with some constraints on their Abelian chief factors.

0.63

Projective blowups: a formal and multicentered proof

cs.LO math.AG ·2026-08-13 ·A. Mayeux
theory similarity 0.49
Abstract

We give a machine-checked proof, in Lean 4, of the universal property of multi- centered blowups: given a finite family Z of closed subschemes of a scheme X, presented on each chart by ideals, there is a scheme BlZ X over X, terminal among X-schemes on which every member of the family becomes an effective Cartier divisor. To the best of our knowledge this is the first formalisation of blowups, single- or multicentered, in any theorem prover. The proof is organised around the universal property of the multicentered dilatation of a ring. The comparison isomorphisms on overlaps, the cocycle identity, and the independence of the chosen presentation are obtained from the uniqueness part of this universal property. We give the exact theorem statement as formalized, the proof architecture, and the main new mathematical ingredients, together with the corresponding Lean code.

0.04

Symmetric List Objects

cs.LO math.CT ·2026-10-27 ·Fiona Blackett, Vikraman Choudhury, Rin Liu
published similarity 0.48
Abstract · Presented at MSFP'26

Cons-lists are fundamental to functional programming, and are well-understood as initial algebras, and as a concrete construction of free monoids. In category theory, such list objects can be axiomatised internal to any monoidal category, with nil and cons maps, and a recursion mechanism. When strengthened to support parametrised recursion, they can be shown to give the free monoid construction. We study a small variant on parametrised list objects called parametrised symmetric list objects, in a symmetric monoidal category, where the two frontmost elements are allowed to be permuted. We show that this gives a construction of free commutative monoids, and develop some related theory.

0.35