Tootfinder

On some Classes of Reversible 2-head Automata
Benedek Nagy (Eastern Mediterranean University / Eszterh\'azy K\'aroly Catholic University), Walaa Yasin (Eastern Mediterranean University)
https://arxiv.org/abs/2507.15317

On some Classes of Reversible 2-head Automata
Deterministic 2-head finite automata which are machines that process an input word from both ends are analyzed for their ability to perform reversible computations. This implies that the automata are backward deterministic, enabling unique forward and backward computation. We explore the computational power of such automata, discovering that, while some regular languages cannot be accepted by these machines, they are capable of accepting some characteristic linear languages, e.g., the language …

Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata
Yonatan Nakar, Dana Ron
https://arxiv.org/abs/2507.14569 …

Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata
We consider the problems of characterizing and testing the stability of cellular automata configurations that evolve on a two-dimensional torus according to threshold rules with respect to the von-Neumann neighborhood. While stable configurations for Threshold-1 (OR) and Threshold-5 (AND) are trivial (and hence easily testable), the other threshold rules exhibit much more diverse behaviors. We first characterize the structure of stable configurations with respect to the Threshold-2 (similarly, …

StackTrans: From Large Language Model to Large Pushdown Automata Model
Kechi Zhang, Ge Li, Jia Li, Huangzhao Zhang, Yihong Dong, Jia Li, Jingjing Xu, Zhi Jin
https://arxiv.org/abs/2507.15343

StackTrans: From Large Language Model to Large Pushdown Automata Model
The Transformer architecture has emerged as a landmark advancement within the broad field of artificial intelligence, effectively catalyzing the advent of large language models (LLMs). However, despite its remarkable capabilities and the substantial progress it has facilitated, the Transformer architecture still has some limitations. One such intrinsic limitation is its inability to effectively capture the Chomsky hierarchy, such as regular expressions or deterministic context-free grammars. Dr…

Transition-based vs stated-based acceptance for automata over infinite words
Antonio Casares
https://arxiv.org/abs/2508.15402 https://arxiv.org/pdf/2508.15…

Transition-based vs stated-based acceptance for automata over infinite words
Automata over infinite objects are a well-established model with applications in logic and formal verification. Traditionally, acceptance in such automata is defined based on the set of states visited infinitely often during a run. However, there is a growing trend towards defining acceptance based on transitions rather than states. In this survey, we analyse the reasons for this shift and advocate using transition-based acceptance in the context of automata over infinite words. We present a …

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, K\'evin Perrot
https://arxiv.org/abs/2509.16065 https:…

Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ cons…

Programmable Anyon Mobility through Higher Order Cellular Automata
Jie-Yu Zhang, Peng Ye
https://arxiv.org/abs/2508.13961 https://arxiv.org/pdf/2508.13961

Programmable Anyon Mobility through Higher Order Cellular Automata
Controlling anyon mobility is critical for robust quantum memory and understanding symmetry-enriched topological (SET) phases with subsystem symmetries (e.g., line-like, fractal, chaotic, or mixed supports). However, a unified framework for anyon mobility in SET phases with such diverse geometric patterns of symmetry supports has remained a major challenge. In this Letter, by introducing higher-order cellular automata (HOCA) -- a powerful computer science tool -- to SET physics, we establish a …

Exploring the Landscape of Non-Equilibrium Memories with Neural Cellular Automata
Ethan Lake, Ehsan Pajouheshgar
https://arxiv.org/abs/2508.15726 https://a…

Exploring the Landscape of Non-Equilibrium Memories with Neural Cellular Automata
We investigate the landscape of many-body memories: families of local non-equilibrium dynamics that retain information about their initial conditions for thermodynamically long time scales, even in the presence of arbitrary perturbations. In two dimensions, the only well-studied memory is Toom's rule. Using a combination of rigorous proofs and machine learning methods, we show that the landscape of 2D memories is in fact quite vast. We discover memories that correct errors in ways qualitatively…

Nonequilibrium protein complexes as molecular automata
Jan Kocka, Kabir Husain, Jaime Agudo-Canalejo
https://arxiv.org/abs/2508.15603 https://arxiv.org/pdf…

Nonequilibrium protein complexes as molecular automata
Biology stores information and computes at the molecular scale, yet the ways in which it does so are often distinct from human-engineered computers. Mapping biological computation onto architectures familiar to computer science remains an outstanding challenge. Here, inspired by Crick's proposal for molecular memory, we analyse a thermodynamically-consistent model of a protein complex subject to driven, nonequilibrium enzymatic reactions. In the strongly driven limit, we find that the system ma…

Replaced article(s) found for nlin.CG. https://arxiv.org/list/nlin.CG/new
[1/1]:
- Generating 3D Terrain with 2D Cellular Automata
Nuno Fachada, Ant\'onio R. Rodrigues, Diogo de Andrade, Phil Lopes

A Myhill-Nerode Type Characterization of 2detLIN Languages
Benedek Nagy (Eastern Mediterranean University / Eszterh\'azy K\'aroly Catholic University)
https://arxiv.org/abs/2507.15316

A Myhill-Nerode Type Characterization of 2detLIN Languages
Linear automata are automata with two reading heads starting from the two extremes of the input, are equivalent to 5' -> 3' Watson-Crick (WK) finite automata. The heads read the input in opposite directions and the computation finishes when the heads meet. These automata accept the class LIN of linear languages. The deterministic counterpart of these models, on the one hand, is less expressive, as only a proper subset of LIN, the class 2detLIN is accepted; and on the other hand, they are also e…

Crosslisted article(s) found for cs.CV. https://arxiv.org/list/cs.CV/new
[2/2]:
- Exploring the Landscape of Non-Equilibrium Memories with Neural Cellular Automata
Ethan Lake, Ehsan Pajouheshgar

Explainable AI-Enhanced Supervisory Control for Robust Multi-Agent Robotic Systems
Reza Pirayeshshirazinezhad, Nima Fathi
https://arxiv.org/abs/2509.15491 https://

Explainable AI-Enhanced Supervisory Control for Robust Multi-Agent Robotic Systems
We present an explainable AI-enhanced supervisory control framework for multi-agent robotics that combines (i) a timed-automata supervisor for safe, auditable mode switching, (ii) robust continuous control (Lyapunov-based controller for large-angle maneuver; sliding-mode controller (SMC) with boundary layers for precision and disturbance rejection), and (iii) an explainable predictor that maps mission context to gains and expected performance (energy, error). Monte Carlo-driven optimization pro…

Proceedings of the Sixteenth International Symposium on Games, Automata, Logics, and Formal Verification
Giorgio Bacci (Aalborg University, Denmark), Adrian Francalanza (University of Malta)
https://arxiv.org/abs/2509.13258

Proceedings of the Sixteenth International Symposium on Games, Automata, Logics, and Formal Verification
This volume contains the proceedings of GandALF 2025, the Sixteenth International Symposium on Games, Automata, Logics, and Formal Verification. GandALF 2025 took place on 16-17th September 2025, in Valletta, Malta. The aim of GandALF 2025 is to bring together researchers from academia and industry who are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-…

Bayesian Inversion via Probabilistic Cellular Automata: an application to image denoising
Danilo Costarelli, Michele Piconi, Alessio Troiani
https://arxiv.org/abs/2507.14869 htt…

Bayesian Inversion via Probabilistic Cellular Automata: an application to image denoising
We propose using Probabilistic Cellular Automata (PCA) to address inverse problems with the Bayesian approach. In particular, we use PCA to sample from an approximation of the posterior distribution. The peculiar feature of PCA is their intrinsic parallel nature, which allows for a straightforward parallel implementation that allows the exploitation of parallel computing architecture in a natural and efficient manner. We compare the performance of the PCA method with the standard Gibbs sampler …

Input-Driven Pushdown Automata with Translucent Input Letters
Martin Kutrib, Andreas Malcher, Matthias Wendlandt
https://arxiv.org/abs/2507.15310 https://a…

Input-Driven Pushdown Automata with Translucent Input Letters
Input-driven pushdown automata with translucent input letters are investigated. Here, the use of translucent input letters means that the input is processed in several sweeps and that, depending on the current state of the automaton, some input symbols are visible and can be processed, whereas some other symbols are invisible, and may be processed in another sweep. Additionally, the returning mode as well as the non-returning mode are considered, where in the former mode a new sweep must start …

Crosslisted article(s) found for nlin.CG. https://arxiv.org/list/nlin.CG/new
[1/1]:
- Exploring the Landscape of Non-Equilibrium Memories with Neural Cellular Automata
Ethan Lake, Ehsan Pajouheshgar

Reinforcement Learning-based Adaptive Path Selection for Programmable Networks
Jos\'e Eduardo Zerna Torres, Marios Avgeris, Chrysa Papagianni, Gergely Pongr\'acz, Istv\'an G\'odor, Paola Grosso
https://arxiv.org/abs/2508.13806

Reinforcement Learning-based Adaptive Path Selection for Programmable Networks
This work presents a proof-of-concept implementation of a distributed, in-network reinforcement learning (IN-RL) framework for adaptive path selection in programmable networks. By combining Stochastic Learning Automata (SLA) with real-time telemetry data collected via In-Band Network Telemetry (INT), the proposed system enables local, data-driven forwarding decisions that adapt dynamically to congestion conditions. The system is evaluated on a Mininet-based testbed using P4-programmable BMv2 sw…

List of Results on the \v{C}ern\'y Conjecture and Reset Thresholds for Synchronizing Automata
Mikhail V. Volkov
https://arxiv.org/abs/2508.15655 https://

List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
We survey results in the literature that establish the Černý conjecture for various classes of finite automata. We also list classes for which the conjecture remains open, but a quadratic (in the number of states) upper bound on the minimum length of reset words is known. The results presented reflect the state of the art as of August 21, 2025.

Supervised and unsupervised learning with numerical computation for the Wolfram cellular automata
Kui Tuo, Shengfeng Deng, Yuxiang Yang, Yanyang Wang, Qiuping A. Wang, Wei Li, Wenjun Zhang
https://arxiv.org/abs/2509.10209

Supervised and unsupervised learning with numerical computation for the Wolfram cellular automata
The local rules of Wolfram cellular automata with one-dimensional three-cell neighborhoods are represented by eight-bit binary that encode deterministic update rules. These automata are widely utilized to investigate self-organization phenomena and the dynamics of complex systems. In this work, we employ numerical simulations and computational methods to investigate the asymptotic density and dynamical evolution mechanisms in Wolfram automata. We apply both supervised and unsupervised learning …

Replaced article(s) found for cs.NE. https://arxiv.org/list/cs.NE/new
[1/1]:
- Neural Cellular Automata for ARC-AGI
Kevin Xu, Risto Miikkulainen
https://

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
Karolina Drabik, Anita D\"urr, Fabian Frei, Filip Mazowiecki, Karol W\k{e}grzycki

Automata Models for Effective Bug Description
Tom Yaacov, Gera Weiss, Gal Amram, Avi Hayoun
https://arxiv.org/abs/2507.11146 https://…

Automata Models for Effective Bug Description
Debugging complex systems is a crucial yet time-consuming task. This paper presents the use of automata learning and testing techniques to obtain concise and informative bug descriptions. We introduce the concepts of Failure Explanations (FE), Eventual Failure Explanations (EFE), and Early Detection (ED) to provide meaningful summaries of failing behavior patterns. By factoring out irrelevant information and focusing on essential test patterns, our approach aims to enhance bug detection and und…

Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability
Sahil Rajesh Dhayalkar
https://arxiv.org/abs/2509.10034 https://

Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability
We present a formal and constructive theory showing that probabilistic finite automata (PFAs) can be exactly simulated using symbolic feedforward neural networks. Our architecture represents state distributions as vectors and transitions as stochastic matrices, enabling probabilistic state propagation via matrix-vector products. This yields a parallel, interpretable, and differentiable simulation of PFA dynamics using soft updates-without recurrence. We formally characterize probabilistic subse…

On Repetitive Finite Automata with Translucent Words
Franti\v{s}ek Mr\'az (Charles University in Prague), Friedrich Otto (Universit\"atKassel)
https://arxiv.org/abs/2507.15315

On Repetitive Finite Automata with Translucent Words
We introduce and study the repetitive variants of the deterministic and the nondeterministic finite automaton with translucent words (DFAwtw and NFAwtw). On seeing the right sentinel, a repetitive NFAwtw need not halt immediately, accepting or rejecting, but it may change into another state and continue with its computation. We establish that a repetitive DFAwtw already accepts a language that is not even semi-linear, which shows that the property of being repetitive increases the expressive ca…

Execution and monitoring of HOA automata with HOAX
Luca Di Stefano
https://arxiv.org/abs/2507.11126 https://arxiv.org/pdf/2507.11126

Execution and monitoring of HOA automata with HOAX
We present a tool called Hoax for the execution of ω-automata expressed in the popular HOA format. The tool leverages the notion of trap sets to enable runtime monitoring of any (non-parity) acceptance condition supported by the format. When the automaton is not monitorable, the tool may still be able to recognise so-called ugly prefixes, and determine that no further observation will ever lead to a conclusive verdict. The tool is open-source and highly configurable. We present its formal foun…

Parallelizable Feynman-Kac Models for Universal Probabilistic Programming
Michele Boreale (University of Florence), Luisa Collodi (University of Florence)
https://arxiv.org/abs/2509.14092

Parallelizable Feynman-Kac Models for Universal Probabilistic Programming
We study provably correct and efficient instantiations of Sequential Monte Carlo (SMC) inference in the context of formal operational semantics of Probabilistic Programs (PPs). We focus on universal PPs featuring sampling from arbitrary measures and conditioning/reweighting in unbounded loops. We first equip Probabilistic Program Graphs (PPGs), an automata-theoretic description format of PPs, with an expectation-based semantics over infinite execution traces, which also incorporates trace weigh…

A critical phase transition in bee movement dynamics can be modeled using a 2D cellular automata
Ivan Shpurov, Tom Froese
https://arxiv.org/abs/2507.11592 …

A critical phase transition in bee movement dynamics can be modeled using a 2D cellular automata
The collective behavior of numerous animal species, including insects, exhibits scale-free behavior indicative of the critical (second-order) phase transition. Previous research uncovered such phenomena in the behavior of honeybees, most notably the long-range correlations in space and time. Furthermore, it was demonstrated that the bee activity in the hive manifests the hallmarks of the jamming process. We follow up by presenting a discrete model of the system that faithfully replicates some o…

Reversibility, balance and expansivity of non-uniform cellular automata
Katariina Paturi
https://arxiv.org/abs/2507.06896 https://arx…

Reversibility, balance and expansivity of non-uniform cellular automata
Non-uniform cellular automata (NUCA) are an extension of cellular automata (CA), which transform cells according to multiple different local rules. A NUCA is defined by a configuration of local rules called a local rule distribution. We examine what properties of uniform CA can be recovered by restricting the rule distribution to be (uniformly) recurrent, focusing on only 1D NUCA. We show that a bijective NUCA with a uniformly recurrent rule distribution is reversible. We also show that if a …

A Cellular Automata Approach to Donation Game
Marcin Kowalik, Przemys{\l}aw Stok{\l}osa, Mateusz Grabowski, Janusz Starzyk, Pawe{\l} Raif
https://arxiv.org/abs/2507.11744

A Cellular Automata Approach to Donation Game
The donation game is a well-established framework for studying the emergence and evolution of cooperation in multi-agent systems. The cooperative behavior can be influenced by the environmental noise in partially observable settings and by the decision-making strategies of agents, which may incorporate not only reputation but also traits such as generosity and forgiveness. Traditional simulations often assume fully random interactions, where cooperation is tested between randomly selected agent…

Replaced article(s) found for nlin.CG. https://arxiv.org/list/nlin.CG/new
[1/1]:
- Deterministic many-body dynamics with multifractal response
Yusuf Kasim, Toma\v{z} Prosen

Efficient Learning of Weak Deterministic B\"uchi Automata
Mona Alluwayma, Yong Li, Sven Schewe, Qiyi Tang
https://arxiv.org/abs/2508.14274 https://arx…

Efficient Learning of Weak Deterministic Büchi Automata
We present an efficient Angluin-style learning algorithm for weak deterministic Büchi automata (wDBAs). Different to ordinary deterministic Büchi and co-Büchi automata, wDBAs have a minimal normal form, and we show that we can learn this minimal normal form efficiently. We provide an improved result on the number of queries required and show on benchmarks that this theoretical advantage translates into significantly fewer queries: while previous approaches require a quintic number of queries…

Expedition & Expansion: Leveraging Semantic Representations for Goal-Directed Exploration in Continuous Cellular Automata
Sina Khajehabdollahi, Gautier Hamon, Marko Cvjetko, Pierre-Yves Oudeyer, Cl\'ement Moulin-Frier, C\'edric Colas
https://arxiv.org/abs/2509.03863

Expedition & Expansion: Leveraging Semantic Representations for Goal-Directed Exploration in Continuous Cellular Automata
Discovering diverse visual patterns in continuous cellular automata (CA) is challenging due to the vastness and redundancy of high-dimensional behavioral spaces. Traditional exploration methods like Novelty Search (NS) expand locally by mutating known novel solutions but often plateau when local novelty is exhausted, failing to reach distant, unexplored regions. We introduce Expedition and Expansion (E&E), a hybrid strategy where exploration alternates between local novelty-driven expansions an…

In which I spelunk through the low-level mechanics of traversing Nondeterministic Finite Automata. ε-closures FTW! https://www.tbray.org/ongoing/When/202x/2025/07/07/Epsilon-Wrangling
I’m sure that the world’s population contains dozens of people w…

QRS: Epsilon Wrangling

Cellular Automata as Generators of Interleaving Sequences
Sara D. Cardell
https://arxiv.org/abs/2506.18848 https://arxiv.org/pdf/2506…

Cellular Automata as Generators of Interleaving Sequences
An interleaving sequence is obtained by combining or intertwining elements from two or more sequences. On the other hand, cellular automata are known to be generators for keystream sequences. In this paper we present two families of one-dimensional cellular automata as generators of interleaving sequences. This study aims to close a notable gap within the current body of literature by exploring the capacity of cellular automata to generate interleaving sequences. While previous works have separ…

Clifford quantum cellular automata from topological quantum field theories and invertible subalgebras
Meng Sun, Bowen Yang, Zongyuan Wang, Nathanan Tantivasadakarn, Yu-An Chen
https://arxiv.org/abs/2509.07099

Clifford quantum cellular automata from topological quantum field theories and invertible subalgebras
We present a general framework for constructing quantum cellular automata (QCA) from topological quantum field theories (TQFT) and invertible subalgebras (ISA) using the cup-product formalism. This approach explicitly realizes all $\mathbb{Z}_2$ and $\mathbb{Z}_p$ Clifford QCAs (for prime $p$) in all admissible dimensions, in precise agreement with the classification predicted by algebraic $L$-theory. We determine the orders of these QCAs by explicitly showing that finite powers reduce to the i…

On the Convergence of Elementary Cellular Automata under Sequential Update Modes
Isabel Donoso-Leiva, Eric Goles, Mart\'in R\'ios-Wilson, Sylvain Sen\'e
https://arxiv.org/abs/2509.07797

On the Convergence of Elementary Cellular Automata under Sequential Update Modes
In this paper, we perform a theoretical analysis of the sequential convergence of elementary cellular automata that have at least one fixed point. Our aim is to establish which elementary rules always reach fixed points under sequential update modes, regardless of the initial configuration. In this context, we classify these rules according to whether all initial configurations converge under all, some, one or none sequential update modes, depending on if they have fixed points under synchronou…

Addition Automata and Attractors of Digit Systems Corresponding to Expanding Rational Matrices
Anjelo Gabriel R. Cruz, Manuel Joseph C. Loquias, J\"org M. Thuswaldner
https://arxiv.org/abs/2507.06158

Addition Automata and Attractors of Digit Systems Corresponding to Expanding Rational Matrices
Let $A$ be an expanding $2 \times 2$ matrix with rational entries and $\mathbb{Z}^2[A]$ be the smallest $A$-invariant $\mathbb{Z}$-module containing $\mathbb{Z}^2$. Let $\mathcal{D}$ be a finite subset of $\mathbb{Z}^2[A]$ which is a complete residue system of $\mathbb{Z}^2[A]/A\mathbb{Z}^2[A]$. The pair $(A,\mathcal{D})$ is called a {\em digit system} with {\em base} $A$ and {\em digit set} $\mathcal{D}$. It is well known that every vector $x \in \mathbb{Z}^2[A]$ can be written uniquely in the…

AP-observation Automata for Abstraction-based Verification of Continuous-time Systems (Extended Version)
Sasinee Pruekprasert, Clovis Eberhart
https://arxiv.org/abs/2509.08343 h…

AP-observation Automata for Abstraction-based Verification of Continuous-time Systems (Extended Version)
A key challenge in abstraction-based verification and control under complex specifications such as Linear Temporal Logic (LTL) is that abstract models retain significantly less information than their original systems. This issue is especially true for continuous-time systems, where the system state trajectories are split into intervals of discrete actions, and satisfaction of atomic propositions is abstracted to a whole time interval. To tackle this challenge, this work introduces a novel trans…

Gaussian concentration bounds for probabilistic cellular automata
Jean-Ren\'e Chazottes, Frank Redig, Edgardo Ugalde
https://arxiv.org/abs/2507.05431 h…

Gaussian concentration bounds for probabilistic cellular automata
We study lattice spin systems and analyze the evolution of Gaussian concentration bounds (GCB) under the action of probabilistic cellular automata (PCA), which serve as discrete-time analogues of Markovian spin-flip dynamics. We establish the conservation of GCB and, in the high-noise regime, demonstrate that GCB holds for the unique stationary measure. Additionally, we prove the equivalence of GCB for the space-time measure and its spatial marginals in the case of contractive probabilistic cel…

An Automaton-based Characterisation of First-Order Logic over Infinite Trees
Massimo Benerecetti (Universit\`a degli Studi di Napoli "Federico II"), Dario Della Monica (Universit\`a degli Studi di Udine), Angelo Matteo (Universit\`a degli Studi di Udine), Fabio Mogavero (Universit\`a degli Studi di Napoli "Federico II"), Gabriele Puppis (Universit\`a degli Studi di Udine)

An Automaton-based Characterisation of First-Order Logic over Infinite Trees
In this paper, we study First Order Logic (FO) over (unordered) infinite trees and its connection with branching-time temporal logics. More specifically, we provide an automata-theoretic characterisation of FO interpreted over infinite trees. To this end, two different classes of hesitant tree automata are introduced and proved to capture precisely the expressive power of two branching time temporal logics, denoted polcCTLp and cCTL*[f], which are, respectively, a restricted version of counti…

[2025-08-22 Fri (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- On finite extensions of lamplighter groups
Corentin Bodart
https://

On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata
Katariina Paturi, Jarkko Kari
https://arxiv.org/abs/2507.06987 https:…

On the surjunctivity and the Garden of Eden theorem for non-uniform cellular automata
Non-uniform cellular automata (NUCA) are an extension of cellular automata with multiple local rules in different cells. We show that if the distribution of local rules is uniformly recurrent, or recurrent in the one-dimensional case, the Garden of Eden theorem holds. We also show that for any non-recurrent distribution, there is a substitution of local rules that defines a NUCA which does not satisfy the Garden of Eden theorem. Finally, we show that a rule distribution asymptotic to recurrent …

Growing Reservoirs with Developmental Graph Cellular Automata
Matias Barandiaran, James Stovold
https://arxiv.org/abs/2508.08091 https://arxiv.org/pdf/2508…

Growing Reservoirs with Developmental Graph Cellular Automata
Developmental Graph Cellular Automata (DGCA) are a novel model for morphogenesis, capable of growing directed graphs from single-node seeds. In this paper, we show that DGCAs can be trained to grow reservoirs. Reservoirs are grown with two types of targets: task-driven (using the NARMA family of tasks) and task-independent (using reservoir metrics). Results show that DGCAs are able to grow into a variety of specialized, life-like structures capable of effectively solving benchmark tasks, stat…

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- A cornering strategy for synchronizing a DFA
Peter Bradshaw, Alexander Clow, Ladislav Stacho

[2025-06-23 Mon (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Emerson-Lei and Manna-Pnueli Games for LTLf and PPLTL Synthesis
Hausmann, Zhu, Parretti, Weinhuber, De Giacomo, Piterman

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Learning Verified Monitors for Hidden Markov Models
Luko van der Maas, Sebastian Junges

[2025-07-23 Wed (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Reduced complexities for sequences over finite alphabets
John M. Campbell, James Currie, Narad Rampersad

[2025-07-22 Tue (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Causal Decompositions of 1D Quantum Cellular Automata
Augustin Vanrietvelde, Octave Mestoudjian, Pablo Arrighi
https://arxiv.org/abs/2506.22219 https://

Causal Decompositions of 1D Quantum Cellular Automata
Understanding quantum theory's causal structure stands out as a major matter, since it radically departs from classical notions of causality. We present advances in the research program of causal decompositions, which investigates the existence of an equivalence between the causal and the compositional structures of unitary channels. Our results concern one-dimensional Quantum Cellular Automata (1D QCAs), i.e. unitary channels over a line of $N$ quantum systems (with or without periodic boundar…

Identity Increases Stability in Neural Cellular Automata
James Stovold
https://arxiv.org/abs/2508.06389 https://arxiv.org/pdf/2508.06389

Identity Increases Stability in Neural Cellular Automata
Neural Cellular Automata (NCAs) offer a way to study the growth of two-dimensional artificial organisms from a single seed cell. From the outset, NCA-grown organisms have had issues with stability, their natural boundary often breaking down and exhibiting tumour-like growth or failing to maintain the expected shape. In this paper, we present a method for improving the stability of NCA-grown organisms by introducing an 'identity' layer with simple constraints during training. Results show that…

[2025-07-22 Tue (UTC), 9 new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-08-22 Fri (UTC), 2 new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-07-23 Wed (UTC), no new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

Characterizing NC1 with Typed Monoids
Anuj Dawar, Aidan T. Evans
https://arxiv.org/abs/2508.11019 https://arxiv.org/pdf/2508.11019

Characterizing NC1 with Typed Monoids
Krebs et al. (2007) gave a characterization of the complexity class TC0 as the class of languages recognized by a certain class of typed monoids. The notion of typed monoid was introduced to extend methods of algebraic automata theory to infinite monoids and hence characterize classes beyond the regular languages. We advance this line of work beyond TC0 by giving a characterization of NC1. This is obtained by first showing that NC1 can be defined as the languages expressible in an extension of …

[2025-09-23 Tue (UTC), 1 new article found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

Replaced article(s) found for nlin.CG. https://arxiv.org/list/nlin.CG/new
[1/1]:
- Temporally Non-Uniform Cellular Automata: Surjectivity, Reversibility and Cyclic Behavior
Subrata Paul, Sukanta Das

Irrational eigenvalues of D-Dimensional Cellular automata
Nassima Ait Sadi, Rezki Chemlal
https://arxiv.org/abs/2509.00933 https://arxiv.org/pdf/2509.00933…

Irrational eigenvalues of D-Dimensional Cellular automata
Cellular automata are dynamical systems defined on lattices and commuting with the Bernoulli shift. In this work, we focus on the spectral properties of D-dimensional cellular automata. We give a characterization of their spectrum from both topological and ergodic point of view. The main results of the paper show the impossibility for a cellular automaton with a fully blocking pattern to have a measurable irrational eigenvalues. Further more, a cellular automaton with a set of equicontinuity po…

[2025-06-23 Mon (UTC), no new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-09-22 Mon (UTC), no new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

How Concise are Chains of co-B\"uchi Automata?
R\"udiger Ehlers
https://arxiv.org/abs/2509.14087 https://arxiv.org/pdf/2509.14087

How Concise are Chains of co-Büchi Automata?
Chains of co-Büchi automata (COCOA) have recently been introduced as a new canonical model for representing arbitrary omega-regular languages. They can be minimized in polynomial time and are hence an attractive language representation for applications in which normally, deterministic omega-automata are used. While it is known how to build COCOA from deterministic parity automata, little is currently known about their relationship to automaton models introduced earlier than COCOA. In this pa…

The theory of reachability in trace-pushdown systems
Dietrich Kuske
https://arxiv.org/abs/2507.15733 https://arxiv.org/pdf/2507.15733

The theory of reachability in trace-pushdown systems
We consider pushdown systems that store, instead of a single word, a Mazurkiewicz trace on its stack. These systems are special cases of valence automata over graph monoids and subsume multi-stack systems. We identify a class of such systems that allow to decide the first-order theory of their configuration graph with reachability. This result complements results by D'Osualdo, Meyer, and Zetzsche (namely the decidability for arbitrary pushdown systems under a severe restriction on the depende…

A Unifying Approach to Picture Automata
Yvo Ad Meeres, Franti\v{s}ek Mr\'az
https://arxiv.org/abs/2509.12077 https://arxiv.org/pdf/2509.12077

A Unifying Approach to Picture Automata
A directed acyclic graph (DAG) can represent a two-dimensional string or picture. We propose recognizing picture languages using DAG automata by encoding 2D inputs into DAGs. An encoding can be input-agnostic (based on input size only) or input-driven (depending on symbols). Three distinct input-agnostic encodings characterize classes of picture languages accepted by returning finite automata, boustrophedon automata, and online tessellation automata. Encoding a string as a simple directed path …

[2025-08-21 Thu (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Active Learning of Symbolic Mealy Automata
Kengo Irie, Masaki Waga, Kohei Suenaga
https://arxiv.org/abs/2509.14694 https://arxiv.org/pdf/2509.14694

Active Learning of Symbolic Mealy Automata
We propose $Λ^*_M$-an active learning algorithm that learns symbolic Mealy automata, which support infinite input alphabets and multiple output characters. Each of these two features has been addressed separately in prior work. Combining these two features poses a challenge in learning the outputs corresponding to potentially infinite sets of input characters at each state. To address this challenge, we introduce the notion of essential input characters, a finite set of input characters that i…

Weighted Automata for Exact Inference in Discrete Probabilistic Programs
Dominik Gei{\ss}ler, Tobias Winkler
https://arxiv.org/abs/2509.15074 https://arxiv…

Weighted Automata for Exact Inference in Discrete Probabilistic Programs
In probabilistic programming, the inference problem asks to determine a program's posterior distribution conditioned on its "observe" instructions. Inference is challenging, especially when exact rather than approximate results are required. Inspired by recent work on probability generating functions (PGFs), we propose encoding distributions on $\mathbb{N}^k$ as weighted automata over a commutative alphabet with $k$ symbols. Based on this, we map the semantics of various imperative programming …

Counting Short Trajectories in Elementary Cellular Automata using the Transfer Matrix Method
C\'edric Koller, Barbora Hudcov\'a
https://arxiv.org/abs/2508.09768 https://…

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Temporally Non-Uniform Cellular Automata: Surjectivity, Reversibility and Cyclic Behavior
Subrata Paul, Sukanta Das

[2025-07-21 Mon (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Active Learning of Mealy Machines with Timers
V\'eronique Bruy\`ere, Bharat Garhewal, Guillermo A. P\'erez, Ga\"etan Staquet, Frits W. Vaandrager

Hexagonal Picture Scanning Automata
Deepalakshmi D, Lisa Mathew
https://arxiv.org/abs/2508.07779 https://arxiv.org/pdf/2508.07779

Hexagonal Picture Scanning Automata
Two new classes of finite automata, called General hexagonal Boustrophedon finite automata and General hexagonal returning finite automata operating on hexagonal grids, are introduced and analyzed. The work establishes the theoretical foundations for these automata models, examines their computational properties, and investigates the relationships and equivalences between the language families they define. The research contributes to the broader understanding of two-dimensional automata theory …

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
Bruno Guillon, Luca Prigioniero, Javad Taheri
https://arxiv.org/abs/2507.11209

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a nondeterministic extension of 2NFAs still characterizing regular languages. The resulting machine is actually a restricted form of 1-LAs -- known as 2NFAs with common guess -- and is self-verifying. A corollary of our construction is that a single exponential is necessary and sufficient for complementing 1-LAs.

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Presheaf automata
Georg Struth, Krzysztof Ziemia\'nski
https://

[2025-08-20 Wed (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

[2025-08-21 Thu (UTC), 1 new article found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

Post-apocalyptic computing from cellular automata
Genaro J. Martinez, Andrew Adamatzky, Guanrong Chen
https://arxiv.org/abs/2508.06035 https://arxiv.org/pd…

Post-apocalyptic computing from cellular automata
Cellular automata are arrays of finite state machines that can exist in a finite number of states. These machines update their states simultaneously based on specific local rules that govern their interactions. This framework provides a simple yet powerful model for studying complex systems and emergent behaviors. We revisit and reconsider the traditional notion of an algorithm, proposing a novel perspective in which algorithms are represented through the dynamic state-space configurations of c…

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- On the Intersection Problem for Quantum Finite Automata
Andrea Benso, Flavio D'Alessandro, Paolo Papi

[2025-09-19 Fri (UTC), no new articles found for nlin.CG Cellular Automata and Lattice Gases]
toXiv_bot_toot

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Exploring Major Transitions in the Evolution of Biological Cognition With Artificial Neural Networks
Konstantinos Voudouris, Andrew Barron, Marta Halina, Colin Klein, Matishalin Patel

Visual Execution and Validation of Finite-State Machines and Pushdown Automata
Marco T. Moraz\'an (Seton Hall University), David Anthony K. Fields (Seton Hall University), Andr\'es M. Garced (Seton Hall University), Tijana Mini\'c (University of Washington)
https://arxiv.org/abs/2508.03641

Visual Execution and Validation of Finite-State Machines and Pushdown Automata
In Formal Languages and Automata Theory courses, students find understanding nondeterministic finite-state and pushdown automata difficult. In many cases, this means that it is challenging for them to comprehend the operational semantics of such machines and, as a consequence, determine why a word is accepted or rejected. This is not entirely surprising, because students are mostly trained to design and implement deterministic programs. Comprehension of pushdown automata is further complicated,…

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Active Learning of Deterministic Transducers with Outputs in Arbitrary Monoids
Quentin Aristote (Universit\'e Paris Cit\'e, CNRS, Inria, IRIF, Paris, France)

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Executable Ontologies: Synthesizing Event Semantics with Dataflow Architecture
Aleksandr Boldachev

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Determination of the fifth Busy Beaver value
The bbchallenge Collaboration, et al.

[2025-08-19 Tue (UTC), 2 new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-09-19 Fri (UTC), 4 new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

Componentwise Automata Learning for System Integration (Extended Version)
Hiroya Fujinami, Masaki Waga, Jie An, Kohei Suenaga, Nayuta Yanagisawa, Hiroki Iseri, Ichiro Hasuo
https://arxiv.org/abs/2508.04458

Componentwise Automata Learning for System Integration (Extended Version)
Compositional automata learning is attracting attention as an analysis technique for complex black-box systems. It exploits a target system's internal compositional structure to reduce complexity. In this paper, we identify system integration -- the process of building a new system as a composite of potentially third-party and black-box components -- as a new application domain of compositional automata learning. Accordingly, we propose a new problem setting, where the learner has direct access…

Verification power of rational-valued automata with deterministic and affine states
Zeyu Chen, Abuzer Yakary{\i}lmaz, Junde Wu
https://arxiv.org/abs/2509.07857 https://

Verification power of rational-valued automata with deterministic and affine states
We investigate the verification power of rational-valued affine automata within Arthur--Merlin proof systems. For one-way verifiers, we give real-time protocols with perfect completeness and tunable bounded error for two benchmark nonregular languages, the balanced-middle language and the centered-palindrome language, illustrating a concrete advantage over probabilistic and quantum finite-state verifiers. For two-way verifiers, we first design a weak protocol that verifies every Turing-recogniz…

Learning Event-recording Automata Passively
Anirban Majumdar, Sayan Mukherjee, Jean-Fran\c{c}ois Raskin
https://arxiv.org/abs/2508.03627 https://arxiv.org/…

Learning Event-recording Automata Passively
This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, LEAP (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an NP-complete problem, and address this with a …

Scalable Learning of One-Counter Automata via State-Merging Algorithms
Shibashis Guha, Anirban Majumdar, Prince Mathew, A. V. Sreejith
https://arxiv.org/abs/2509.05762 https://

Scalable Learning of One-Counter Automata via State-Merging Algorithms
We propose One-counter Positive Negative Inference (OPNI), a passive learning algorithm for deterministic real-time one-counter automata (DROCA). Inspired by the RPNI algorithm for regular languages, OPNI constructs a DROCA consistent with any given valid sample set. We further present a method for combining OPNI with active learning of DROCA, and provide an implementation of the approach. Our experimental results demonstrate that this approach scales more effectively than existing state-of-t…

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- A Hierarchy of Nondeterminism
Bader Abu Radi, Orna Kupferman, Ofer Leshkowitz
https…

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Enhanced Data Race Prediction Through Modular Reasoning
Zhendong Ang, Azadeh Farzan, Umang Mathur

[2025-09-18 Thu (UTC), 1 new article found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-07-18 Fri (UTC), no new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)
Luk\'a\v{s} Hol\'ik, Ond\v{r}ej Leng\'al, Juraj Major, Ad\'ela \v{S}t\v{e}pkov\'a, Jan Strej\v{c}ek
https://arxiv.org/abs/2507.03439

On Complementation of Nondeterministic Finite Automata without Full Determinization (Technical Report)
Complementation of finite automata is a basic operation used in numerous applications. The standard way to complement a nondeterministic finite automaton (NFA) is to transform it into an equivalent deterministic finite automaton (DFA) and complement the DFA. The DFA can, however, be exponentially larger than the corresponding NFA. In this paper, we study several alternative approaches to complementation, which are based either on reverse powerset construction or on two novel constructions that …

Replaced article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Unsupervised Automata Learning via Discrete Optimization
Lutz, Kaminskyi, Wittbold, Dierl, Howar, K\"onig, M\"uller, Neider

Crosslisted article(s) found for cs.FL. https://arxiv.org/list/cs.FL/new
[1/1]:
- Executable Ontologies: Synthesizing Event Semantics with Dataflow Architecture
Aleksandr Boldachev

[2025-09-17 Wed (UTC), 1 new article found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot

[2025-07-17 Thu (UTC), 2 new articles found for cs.FL Formal Languages and Automata Theory]
toXiv_bot_toot