Formal Languages and Automata Theory
See recent articles
Showing new listings for Friday, 20 November 2026
- [1] arXiv:2611.24978 [pdf, html, other]
-
Title: Axioms of PhyllotaxisBurghard Herrmann (Free University Berlin)Comments: Colloquium Logicum 2026Subjects: Formal Languages and Automata Theory (cs.FL)
Observations of simultaneous occurrence of new objects in the early developmental stage of flower heads challenge the classical model of phyllotaxis. Prusinkiewicz (2026) applies Lindenmayer's axiomatic approach to a model of the initial expansion stage and explains the origin of the divergence angle 137.5°, a characteristic by which the classical model consistently demonstrates its validity. This paper proposes a generalised axiomatic model of initial expansion and applies it to a handful of relevant divergence angles.
- [2] arXiv:2611.25186 [pdf, html, other]
-
Title: Leveraging Restrictions to Optimize Register Automata LearningComments: 36 pages, 6 figures, to appear in VMCAI 2027Subjects: Formal Languages and Automata Theory (cs.FL)
Active automata learning algorithms, especially those that are able to learn extended finite state machines, such as register automata, can capture the behavior of complex systems and help analyses that uncover critical bugs in them. However, the performance and scalability of these algorithms often becomes an issue when models increase in size.
$SL^{\lambda}$, the current state-of-the-art algorithm for learning register automata, uses a cost-efficient data structure with mechanisms for computing short and restricted tests. In this paper, we present $SL^{\lambda}_{=}$, an extension of $SL^{\lambda}$ for the theory of equality, which improves scalability by employing knowledge gained from prior tests at subsequent steps to restrict future tests to only those that are necessary to achieve progress in the next step.
We have implemented $SL^{\lambda}_{=}$ as a new algorithm in RALib, and evaluate its performance by comparing it against $SL^{*}$ and $SL^{\lambda}$ on a series of benchmarks, including five widely used implementations of DTLS servers. Our evaluation shows that $SL^{\lambda}_{=}$ needs significantly fewer tests than $SL^{*}$ and $SL^{\lambda}$ to infer models of systems, and scales clearly better than them. - [3] arXiv:2611.26143 [pdf, html, other]
-
Title: Revisiting Finiteness of Matrix MonoidsComments: 17 pages, published at ICALP 2026Subjects: Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO)
This paper concerns decision problems related to finite monoids of rational matrices. We show that determining finiteness of a given finitely presented monoid is in PSPACE, improving the known $\text{co}{-}\text{NEXP}^{\text{NP}}$ bound. We also show that the membership problem for finite matrix monoids is PSPACE-complete, improving the known NEXP-upper bound. Our two complexity results are corollaries of a new polynomial bit-size bound on matrix entries in finite monoids. This is obtained by reduction to the case of matrix groups, using the structure theory of noncommutative algebras and of matrix monoids. Our techniques also give us a polynomial-time algorithm for deciding whether a monoid of rational matrices is conjugate to a monoid of integer matrices.
- [4] arXiv:2611.26535 [pdf, html, other]
-
Title: Complete Test Suites for Effectful AutomataSubjects: Formal Languages and Automata Theory (cs.FL)
Complete test suites for automata are (finite) sets of words that enable testing an implementation against a specification: when a (black-box) automaton passes the test suite, completeness guarantees that it is equivalent to the specification on all (infinitely many) words. A well-known method for constructing complete test suites for deterministic automata is the W-method, used in conformance testing and automata learning.
Based on a recent categorical generalisation of the W-method, we propose a framework for~the construction and analysis of test suites for a certain class of effectful automata defined by commutative monads. By working in the Eilenberg-Moore category of the associated monad at hand, we obtain a generic notion of effectful W-method, together with a completeness theorem. We show how to apply the framework and derive complete test suites for non-deterministic and weighted automata.
New submissions (showing 4 of 4 entries)
- [5] arXiv:2611.25003 (cross-list from cs.LG) [pdf, html, other]
-
Title: A Model of Diverse Sampling from Language ModelsComments: NeurIPS 2026 paperSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Formal Languages and Automata Theory (cs.FL); Machine Learning (stat.ML)
Language models often produce high-quality individual samples but poor sets, with repeated samples clustering around the same semantic modes. We formalize diverse generation as sampling a size-$K$ subset of complete strings from a determinantal point process (DPP), where the likelihood encodes item quality, and the embedding geometry encodes repulsion between similar outputs. Exact inference over all strings is intractable, so we propose PoolDPP: draw a finite candidate pool from a tractable proposal, importance-weight the candidates toward the target quality, and run a $K$-DPP sampler on the induced pool kernel; a greedy MAP variant provides deterministic selection. We prove a finite-sample bound with an explicit constant: the KL divergence between the sampler's output and the target $K$-DPP decays as O(1/N) in the pool size. Empirically, PoolDPP extends the quality--diversity frontier on open-ended generation and the precision--recall frontier on ambiguous text-to-SQL (Ambrosia), and on mathematical reasoning (GSM8K), it raises diversity at about the same pass@$K$.
- [6] arXiv:2611.26102 (cross-list from cs.LO) [pdf, html, other]
-
Title: Burnside Problems for Matrix Semigroup Quotients with Applications to Border ComplexityComments: 51 pages, submitted to STOC 2027Subjects: Logic in Computer Science (cs.LO); Formal Languages and Automata Theory (cs.FL)
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.
Cross submissions (showing 2 of 2 entries)
- [7] arXiv:2605.09435 (replaced) [pdf, html, other]
-
Title: Star Complexity of Parikh Images of Languages over Infinite AlphabetsComments: Full version of LICS 2026Subjects: Formal Languages and Automata Theory (cs.FL)
Parikh's theorem identifies the commutative images of regular and context-free languages over finite alphabets. We study the commutative images of quasi-regular and quasi-context-free languages over infinite alphabets, these are the languages that are accepted by the corresponding automata models augmented with registers. Over finite alphabets commutative images of regular languages are known to be precisely the semilinear sets, over infinite alphabets the corresponding algebraic sets are called rational sets of data vectors. In contrast to semilinear sets, nesting stars in rational sets add expressive power and thus star-height is a measure of complexity for this sets.
It was previously established that languages accepted by one-register automata or one-register binary branching context-free grammars have rational commutative images. We refine this result by proving that the star-height of the commutative image of any one-register automaton is at most two. Using this extension, we prove rationality for all one-register context-free grammars, with arbitrary branching degree.
Furthermore, we show that quasi-regular languages can have irrational commutative images already for a language accepted by a three-register automaton. Finally, we show that quasi-context-free languages can have commutative images that are different from the commutative image of any quasi-regular language, where the separation is witnessed again with three registers. Thus we conclude that Parikh's theorem fails over infinite alphabets for automata with registers. - [8] arXiv:2610.33131 (replaced) [pdf, html, other]
-
Title: Locally eventually onto cellular automataComments: 33 pages, minor revisionSubjects: Formal Languages and Automata Theory (cs.FL); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Dynamical Systems (math.DS); Cellular Automata and Lattice Gases (nlin.CG)
We give a new checkable criterion to ensure that a one-dimensional cellular automaton on a finite alphabet is open and 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 open and 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 open and locally eventually onto. The appendix provides the algorithms that check these finite criteria and then presents examples of open, locally eventually onto, non-bipermutive cellular automata for small diameters.
- [9] arXiv:2408.14443 (replaced) [pdf, html, other]
-
Title: Ensemble LogicSubjects: Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL)
Ensemble Logic (EL) is a family of modal logics whose modal parameters are terms with quantified variables. We interpret formulas over metric monoids, that is, commutative monoids equipped with translation-invariant metrics. Displacement evaluates a formula at a translated point, while bounded existence and bounded universality evaluate it at some or every point of a window of prescribed length. Quantification over points and lengths allows the same variable to occur in the parameters of several operators. This provides a common framework for temporal and spatial reasoning in discrete, dense and multi-dimensional settings. Our main result establishes a sharp undecidability boundary for satisfiability over the natural numbers: satisfiability is undecidable already for formulas $\exists N\,\exists n\,\Psi$ in which $\Psi$ is built from the letters of a fixed alphabet by conjunction, disjunction, displacement and bounded universality. We prove this by a reduction from Post's Correspondence Problem. We also present results, in part from companion work, that place this theorem in the general theory of EL. These include an atomic-displacement normal form for covariant windows and composition laws for discrete and dense time. The discrete logic admits an embedding of linear temporal logic, defines the accepting runs of every Büchi automaton, and has a sound equational calculus. For the rational logic, we show that every fixed formula can be evaluated in polynomial time on interval models in which atomic propositions are interpreted by finite unions of intervals. Finally, we represent timed words over positions and real time and compare two window geometries; with rectangular windows, two shared lengths yield undecidability on finite timed words.