CS Paper Radar

Shortest Synchronizing Words on Product Automata

Henning Fernau, Igor Rystsov

cs.FL ·submitted 2026-11-06 08:09 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Synchronizing Automata: Open Problems

cs.FL ·2026-08-25 ·Marek Szykuła
publishedsurveyhot directionhighly cited similarity 0.74
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We survey selected open problems in the theory of synchronizing automata, centered around the famous Černý conjecture. A deterministic finite automaton is called synchronizing if it admits a reset word whose action maps all states to a single state. The Černý conjecture states that every synchronizing automaton with n states possesses a reset word of length at most (n-1)^2. We discuss avoiding words, compressing a state with another, synchronization of a (given or any) subset, complexity of deciding the synchronizability, average reset threshold, and linear-algebraic methods. Some new auxiliary results are also presented.

0.72

On smallest synchronizing terms over constant alphabets

cs.FL ·2026-09-01 ·Luisa Herrmann, Richard Mörbitz
theory similarity 0.68
Abstract

We show a subexponential lower bound on the reset threshold of synchronizing deterministic finite tree automata (DTA) over alphabets of just two symbols. This significantly improves the previous one, which was quadratic in the number of states. Our result also narrows the gap towards the lower bound for DTA over alphabets that grow linearly with the number of states, as well as the best known upper bound, both of which are currently exponential.

0.08

Proceedings 17th International Conference on Automata and Formal Languages

cs.FL cs.CC ·2026-08-24 ·Michal Hospodár, Galina Jirásková, Viktor Olejár, Juraj Šebej, György Vaszil
publishedhot direction similarity 0.67
Abstract

The 17th International Conference on Automata and Formal Languages (AFL 2026) was held in Košice, September 7-10, 2026. It was organized by the Faculty of Science, P. J. Šafárik University in Košice and the Mathematical Institute of the Slovak Academy of Sciences. This volume contains the texts of the three invited lectures and the 18 papers selected by the Program Committee from a total of 27 submissions. The accepted papers, submitted by authors from 14 countries, cover all important areas of automata and formal language theory and their applications such as grammars and acceptors for strings, trees, and graphs, algebraic theories and algorithms for automata and languages, decision problems, relations to complexity theory, picture description and analysis, and other fields.

0.53

Efficient Nominal Automata Computation with Strong Nominal Sets

cs.FL ·2026-11-17 ·Hiroya Fujinami
similarity 0.66
Abstract · 47 pages

Nominal automata and register automata are expressively equivalent models of computation over infinite alphabets, yet an algorithmic gap separates them in practice: dedicated algorithms decide language equivalence of deterministic register automata in polynomial time by working orbit-wise, while general-purpose nominal-computation tools that rely on SMT solvers hide the orbit structure and degrade rapidly even on small instances. We trace this gap to non-trivial local symmetries in nominal sets and observe that the configuration spaces of register automata correspond to strong nominal sets, whose elements carry only trivial local symmetries. We characterize strong nominal sets categorically, consolidating known and new equivalences, and derive a constraint-free array representation of orbit-finite strong nominal sets and equivariant maps; we further prove the existence of projective covers, guaranteeing that every nominal set admits a strong approximation preserving both orbit count and dimensions, computable for quotients of strong nominal sets. Building on these results, we develop concrete algorithms for language equivalence, minimization, and active learning, bridging the algorithmic gap for equivalence (in polynomial time for a fixed alphabet dimension) and extending the orbit-wise approach to minimization and learning. Finally, our implementation Namae, based on the array representation, outperforms existing nominal-computation tools and, at scale, stays within a small constant factor of a dedicated register-automaton equivalence tool.

0.47

Graphoid Automata, Frobenius PROPs, and Semiring Evaluation

cs.FL math.CT ·2026-10-02 ·Antonios Kalampakas
theory similarity 0.64
Abstract · 29 pages

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.

0.27

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.64
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

A turn or reversal in a computation of a pushdown automaton is a switch from a phase in which the height of the pushdown store increases to a phase in which it decreases. Given a pushdown automaton, we first consider, for each string in its language, the minimum number of turns made in accepting computations (weak measure). We prove that it is decidable whether a pushdown automaton accepts a bounded language in a constant number of turns and whether it accepts a bounded language in k turns, for any given k>=0. This is in contrast to the general case, in which these problems are known to be undecidable, with the exception of acceptance in 0 turns, which is decidable. Furthermore, we prove that when the number of turns sufficient to accept a bounded language is not limited by any constants, it linearly grows with respect to the input length. Also this is in contrast with the general case where, for each nonnegative k, there exists a language for which the number of turns necessary and sufficient is of the order of log^(k), the k times composition of the logarithm with itself. We also prove that, when the costs of all accepting computations are taken into account (accept measure), a linear lower bound for the number of turns, if not limited by any constants, holds even removing the restriction to bounded languages.

0.43

Graph-based automata

cs.FL math.CO ·2026-09-08 ·Cyril Pujol
theory similarity 0.63
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

Every Regular Language Has a Bipartite Cactus Automaton

cs.FL ·2026-10-08 ·Mario Grobler, Till Koziel, Sebastian Siebertz
published similarity 0.63
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