CS Paper Radar

Defining the Crick-Franklin-Watson genes of any robot (equals a finite state machine) and defining the Shannon genetic code attached to each gene. We also define the Krohn-Rhodes complexity of any regular maximal prefix code

John Rhodes

cs.FL math.PR ·submitted 2026-08-29 06:56 UTC · v1

Abstract

This paper will discuss the relationships among three pillars of mathematics: important research in codes and automata by Marcel-Paul Schutzenberger and others; random walks on finite semigroups by Persi Diaconis and others; and advanced techniques from finite semigroup theory used in proving Krohn-Rhodes complexity c is decidable by Stuart Margolis, Anne Schilling, and myself. Very surprising connections exist between the Fundamental Lemma of Complexity c (epimorphisms between finite semigroups that are one-to-one on subgroups preserve c) and coupling from the past in Markov chains, Diaconis' strong stationary time, and the Crick-Franklin-Watson genes of a finite automaton (which will be defined in the paper).

Comment
13 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Towards A Parametrized Complexity of Determinization

cs.FL ·2026-11-07 ·Ivan Baburin, Ryan Cotterell
similarity 0.62
Abstract

Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is \textsf{PSPACE}-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, \emph{any} determinization algorithm which runs at least as fast. This result implies that making any \textit{a priori} estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this---in the spirit of parametrized complexity---we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce \emph{subset complexity}---a refinement of the semigroup complexity which has a tighter connection with the subset construction. In certain scenarios, the subset complexity can be approximated in polynomial time, making it potentially viable for more practical applications.

0.25

The smallest programmable machine and the hardness of analyzing it

cs.CC ·2026-10-07 ·J. Andres Montoya
theory similarity 0.59
Abstract

We investigate the computational complexity of analyzing the structural and behavioral properties of deterministic k-pebble automata, which represent a natural framework for studying minimal programmable machines. First, we provide an explicit construction of a three-pebble automaton U capable of simulating any deterministic finite automaton (DFA) on a given input word, establishing a link between pebble automata capabilities, Kolmogorov complexity, and automatic complexity. Next, we restrict our architectural framework to two-pebble programmable machines U(2,N) simulating DFAs with at most N states. We analyze the decision problem ANAL(U(2,5)), which asks whether a five-state program can separate two distinct finite words. By establishing a polynomial-time reduction from the quasi-identity checking problem for finite semigroups, we prove that ANAL(U(2,5)) is NP-complete. Finally, we explore the complexity of separating binary strings under the Exponential Time Hypothesis (ETH), showing how computational hardness implies polynomial lower bounds for the size of the smallest DFAs separating binary strings.

0.29

Shortest Synchronizing Words on Product Automata

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

How Can Size, Ceiling, and Time Bounds Affect the Complexity of Nonuniform Automata Families?

cs.CC cs.FL ·2026-11-16 ·Tomoyuki Yamakami
similarity 0.56
Abstract · (A4 size, 10pt, 34 pages, 6 figures) This paper is a modified, extended version of arxiv.org/abs/2606.26685v1 (2026). This paper is an exten…

In the past literature, families of two-way finite automata and pushdown automata having limited resource-bounded complexity have been studied in direct connection to (mainstream) space-bounded complexity classes equipped with Karp-Lipton style advice of limited size when all inputs given to the automata have bounded length. We acknowledge three major factors--size, ceiling, and time--of such families, which have a significant impact on the computational/descriptional complexity of finite and pushdown automata families, where the "size" refers to the (stack-)state complexity, the "ceiling" refers to the maximum input length, and the "time" refers to the execution time of underlying automata. In this line of study, we further explore these effects caused by different sizes and ceilings. We exploit automata-based reducibility and translatability to space-bounded advised Turing machines and auxiliary automata.

0.44

Turn Complexity and Bounded Languages

cs.FL ·2026-08-25 ·Giovanni Pighizzini
publishedtheoryhot direction similarity 0.56
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

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.55
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

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.55
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

Burnside Problems for Matrix Semigroup Quotients with Applications to Border Complexity

cs.LO cs.FL ·2026-11-19 ·Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, James Worrell
theory similarity 0.54
Abstract · 51 pages, submitted to STOC 2027

The Burnside theorem for matrix semigroups states that a finitely generated matrix semigroup is finite whenever each element has only finitely many distinct powers. We study analogous finiteness questions for quotients of matrix semigroups by congruences, which need not themselves admit faithful finite-dimensional matrix representations. We show three finiteness criteria based on uniform bounds on the quotient images of (rank-)stable subsemigroups and groups in the Zariski closure. Our proofs use exterior algebra and the Ramsey theorem to develop variations of Simon's factorisation forest to matrix semigroups modulo congruences. We also present applications of our results to border complexity. One such involves separating homogeneous algebraic branching programs of fixed width and degree from its Zariski closure.

0.37