CS Paper Radar

Graphoid Automata, Frobenius PROPs, and Semiring Evaluation

Antonios Kalampakas

cs.FL math.CT ·submitted 2026-10-02 18:10 UTC · v1
theory

Abstract

Graphoid automata evaluate graphs by composing relations between words of states. We examine the equations that make this evaluation independent of the chosen graph expression, and what changes when relations are replaced by matrices over a commutative semiring. We prove that the classical graphoid equations are equivalent to the special commutative Frobenius equations together with the required symmetry laws. The known cospan and hypergraph presentations then describe equality of structural and labelled expressions, with the bone law deleting precisely the isolated internal vertices. We use established partition representations to compare this equality with equality of evaluated matrices. For any nonempty finite state set $Q$ and commutative semiring $K$, we give a uniform criterion for two structural expressions to have the same matrix. The criterion determines which isolated-vertex counts are distinguished and when a vanishing scalar makes matrices from different boundary partitions equal. For the canonical structure, the bone law holds precisely when $|Q|\cdot1_K=1_K$. Preserving all relational compositions is a separate requirement, equivalent to additive idempotency for $|Q|\geq2$. We then examine the characteristic matrices of the known relational structures on $Q$ given by disjoint unions of Abelian groups. Their Frobenius equations hold over every commutative semiring, whereas specialness depends on the order of each group and the bone law depends on the number of groups. These conditions specify which equations remain valid when weights are assigned to a graphoid automaton.

Comment
29 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Automatic constraints with few subpowers and graphoid recognition

cs.LO cs.FL ·2026-09-07 ·Antonios Kalampakas
theory similarity 0.64
Abstract · 23 pages, 2 figures. Reproducibility package: https://doi.org/10.5281/zenodo.22648283

Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting.

0.42

Shortest Synchronizing Words on Product Automata

cs.FL ·2026-11-06 ·Henning Fernau, Igor Rystsov
similarity 0.64
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

Solving polynomial equations over partial discrete dynamical systems

cs.DM ·2026-09-30 ·Maximilien Gadouleau, Sara Riva, Marius Rolland, Marie-Emile Voge
similarity 0.63
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

Graph-based automata

cs.FL math.CO ·2026-09-08 ·Cyril Pujol
theory similarity 0.62
Abstract

We study graph-based automata: nondeterministic finite automata obtained from edge-colored or oriented graphs by taking every vertex as both initial and accepting, and every edge as a pair of opposite transitions. The language of these automata corresponds to the set of edge-colored or oriented paths mapping to their corresponding graphs. We develop an analogous notion for trees and characterise the languages recognised by these models. For tree languages we prove the existence of a unique size- minimal graph and, more generally, a homomorphism-minimal graph for both word and tree languages using duality methods. In order to further motivate these models, we showcase a few results at the inter- section between graph theory and automata theory: We relate graph-based automata to reversible automata, give a decomposition of graph-based languages into reversible languages, and introduce the remanent language of an undirected graph as the inter- section of all its orientations. This remanent language captures structural information on the graph such as chromatic number.

0.19

The Value Generating Power of Weighted Tree Automata with Initial Algebra Semantics

cs.FL ·2026-08-25 ·Manfred Droste, Zoltán Fülöp, Andreja Tepavčević, Heiko Vogler
published similarity 0.60
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the generating power of the initial algebra semantics of weighted tree automata over strong bimonoids (hence also over semirings) and the question under which conditions the weighted tree automata can produce only finitely many values. We show that there exists a right-distributive strong bimonoid which is bi-locally finite but not locally finite. We also show that if the ranked alphabet contains a symbol with rank at least two, then for any finitely generated strong bimonoid, weighted tree automata can generate, via their initial algebra semantics, all elements of the strong bimonoid. As a consequence of these results, for bi-locally finite right-distributive strong bimonoids which are not locally finite, weighted tree automata can generate infinitely many values, provided that the input ranked alphabet contains a symbol with rank at least two. This is in sharp contrast to the setting of weighted string automata, which can generate only finitely many values. As a further consequence, for any finitely generated semiring, there exists a weighted tree automaton which generates, via its run semantics, all elements of the semiring.

0.72

Locally eventually onto cellular automata

cs.FL cs.DMmath.COmath.DS+1 ·2026-10-23 ·Jan Kristian Haugland, Nadia S. Larsen, Tron Omland, Henrikke G. Rustad
similarity 0.59
Abstract · 29 pages

We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is locally eventually onto. In this setting, openness is equivalent to being n-to-1 for some n and therefore implies surjectivity. Bipermutive cellular automata are known to be locally eventually onto, while open cellular automata that are neither bipermutive nor bijective appear to have received less attention. Building on Sutner's work with de Bruijn graphs, we describe a method for deciding openness and at the same time determining n. We then introduce the notion of block-regularity of local rules as a generalization of bipermutivity and prove that it implies openness. We further identify two conditions that, together with block-regularity, ensure that every nonempty cylinder set is mapped onto the whole configuration space after a finite number of iterations, and hence that the cellular automaton is locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of locally eventually onto, non-bipermutive cellular automata for small diameters.

0.27

Every Regular Language Has a Bipartite Cactus Automaton

cs.FL ·2026-10-08 ·Mario Grobler, Till Koziel, Sebastian Siebertz
published similarity 0.59
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

0.32

Functorial Analysis of Group-Alphabet Cellular Automata

cs.FL math.GRmath.COmath.CT+1 ·2026-10-29 ·François Huard, Nathan Dion Larivière
similarity 0.58
Abstract

Let $G$ be a group and let $n\in\mathbb N$. We consider one-dimensional cellular automata of length $n$ over the alphabet $G$, with periodic boundary conditions and with local rules $φ$ given by words. We construct a functor $F$ from $\mathbf{Grp}$, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category $\mathcal C_{n,φ}$ of state transition graphs of all such group-alphabet cellular automata, and show $F$ is an equivalence onto this category. Consequently we investigate the translation of categorical structures in $\mathbf{Grp}$ in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in $\mathcal C_{n,φ}$ is given, together with a formula for cycle lengths and multiplicities in this product. When $G$ is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.

0.19