CS Paper Radar

Testing and Learning Symbolic Finite State Machines

Wen-ling Huang, Jan Peleska

cs.FL cs.SE ·submitted 2026-09-22 02:51 UTC · v1
theory

Abstract

Symbolic finite state machines (SFSMs) describe input/output behaviour using guards and output assignments with possibly infinite data domains. We study deterministic and completely specified SFSMs whose guards and output assignments depend only on the current input. We define finite representative input sets that contain witnesses for relevant guard overlaps and separating witnesses for output assignments that differ on those overlaps. Our main theorem shows that language equivalence of the finite instantiations implies language equivalence over the full input domain. This result transfers complete testing methods for deterministic finite state machines (DFSMs) to SFSMs, provided finite sets of admissible guards and output assignments and an upper bound on the number of distinguishable reachable states are known. Under these assumptions, a DFSM learner with complete testing can learn a finite instantiation, which is then lifted to an equivalent SFSM. We establish a bound on the size of representative input sets and give an SMT construction whose correctness and termination hold under stated solver assumptions.

Closest papers

Nearest neighbours by meaning across the whole index.

Leveraging Restrictions to Optimize Register Automata Learning

cs.FL ·2026-11-18 ·Paul Fiterau-Brostean, Bengt Jonsson, Konstantinos Sagonas, Fredrik Tåquist
publishedhot direction similarity 0.64
Abstract · 36 pages, 6 figures, to appear in VMCAI 2027

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^λ$, 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^λ_{=}$, an extension of $SL^λ$ 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^λ_{=}$ as a new algorithm in RALib, and evaluate its performance by comparing it against $SL^{*}$ and $SL^λ$ on a series of benchmarks, including five widely used implementations of DTLS servers. Our evaluation shows that $SL^λ_{=}$ needs significantly fewer tests than $SL^{*}$ and $SL^λ$ to infer models of systems, and scales clearly better than them.

0.56

Learning Canonical Register Automata over Ordered Data Domains

cs.CL cs.LG ·2026-08-19 ·Yong Li, Qiyi Tang, Di-De Yen
similarity 0.62
Abstract

Register automata are finite automata equipped with memory that recognize data languages over infinite alphabets. In this work, we investigate active learning algorithms for deterministic register automata (DRAs) over ordered data domains--covering both dense domains, such as the rationals, and non-dense domains such as the integers. We show that the active learning problem for DRAs over both dense and non-dense ordered domains can be treated within a single unified framework. More specifically, we develop and implement a polynomial-time active learning procedure for DRAs over ordered domains, using oracles for membership, equivalence and memorability queries. The memorability queries were originally introduced for learning DRAs over domains with identity tests. Our unified framework also leads to a new consequence: minimization of DRAs over the non-dense ordered domain of integers is decidable, extending a result previously known only for dense domains. Finally, we give improved complexity bounds of several decision problems for DRAs over ordered domains that are closely related to the queries used in active learning.

0.27

Deterministic Bandwidth of Finite Languages

cs.FL ·2026-08-25 ·Da-Jung Cho, Szilárd Zsolt Fazekas, Max Wiedenhöft
publishedtheory similarity 0.61
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

Bandwidth restricts how far transitions can move under an ordering of the states in an automaton. While every finite language admits a bandwidth-2 NFA representation, the deterministic setting is substantially more restrictive. We investigate the bandwidth of partial DFAs accepting finite languages. We show that bounded bandwidth imposes strong structural restrictions on deterministic representations. We prove that there is an infinite hierarchy of classes of finite languages defined by deterministic bandwidth. As a special case of interest, we consider finite languages accepted by bandwidth-1 partial DFAs, and show that they admit a positional characterization, which yields a polynomial-time decision algorithm. We further study how the minimum DFA bandwidth can be estimated from the structure of the minimal DFA. We derive computable upper and lower bounds based on position-unfolding, and local growth of reachable residual states. These bounds can be computed efficiently and differ by at most a linear factor in the maximum word length. We also present a simple language family where the bounds match exactly.

0.48

From k+1 to k heads the descriptive trade-off is non-recursive

cs.FL ·2026-10-08 ·Christos Kapoutsis
theoryhot directionhighly cited similarity 0.60
Abstract · Proceedings of DCFS 2004, pp. 213-224. Number of pages: 13. Number of figures: 0

We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.

0.61

Parameterized Reachability for Register Machines with Data

cs.FL ·2026-10-06 ·Parosh Aziz Abdulla, Mohammed Faouzi Atig, Abhijith R Nair, K Narayan Kumar, Prakash Saivasan
similarity 0.60
Abstract

We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set of local registers, the communication across machines is mediated through a set of shared registers. Both local and shared registers can take values from an infinite data domain. The program's primitive operations include copying values between registers, assigning constants, comparing registers for (dis-)equality, and nondeterministic assignments that store an arbitrary domain value into a local register. The parameterized reachability problem considers a program and a target location, asking whether there exists some n in Naturals such that an execution of n identical machines (referred to as instances) results in at least one instance reaching the specified location. We show that this problem is Pspace-complete in the general case and it becomes undecidable if a freshness assumption (i.e., each assignment must produce a unique value distinct from all constants) is applied to nondeterministic assignments. This undecidability persists even for systems restricted to two shared and two local registers. Finally, we establish optimal decidability results for two restricted settings: when each thread is limited to a single local register, or when the system utilizes only one shared register.

0.30

Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

cs.FL cs.LO ·2026-11-06 ·Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, Paweł Parys
top venuetheory similarity 0.60
Abstract

Rabin's Tree Theorem says that the MSO theory of the infinite binary tree $2^*$ is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to $2^{\le ω}$, i.e. by allowing quantification over sets of infinite branches. A longstanding open problem is whether the decidability can be recovered in $2^{\le ω}$ by restricting set quantification to Borel sets. We make some progress in this direction, by identifying a suitable automaton model, and showing that most of the automata-theoretic approach to Rabin's Theorem can be extended to the new framework. The only missing part is a conjecture about finite-memory determinacy in certain games. This paper states and explores the conjecture. We prove it in some restricted cases, and give lower bounds on the memory required in those games.

0.70

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

cs.FL cs.LG ·2026-09-09 ·Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
code/data similarity 0.60
Abstract · v2: fixed a typo in abstract title; added a figure in abstract page; added connections to known sufficient conditions; added a normalization…

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization

0.67

Bridging the Gap Between Plain VASS and Branching VASS

cs.LO cs.FL ·2026-09-14 ·Clotilde Bizière, Jérôme Leroux, Grégoire Sutre
publishedtheory similarity 0.60
Abstract · 25 pages, extended version of the paper with same title and same authors presented at FOSSACS'26

Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable reachability problem for VASS has many applications in logic, automata, and verification. In this paper we study the reachability problem for BVASS, a branching generalization of VASS. We show that BVASS reachability sets are very similar to VASS reachability sets, namely that they are sections of VASS. Our proof relies on a new well-quasi-order (wqo) on BVASS runs that generalizes the well-known wqo on VASS runs. By leveraging an amalgamation property, we prove that every BVASS run can be transformed into an equivalent one of bounded branching complexity. This allows us to derive several results on the geometry of BVASS reachability sets. As an application we obtain that reachability sets of 5-dimensional BVAS are effectively semilinear, as is the case for 5-dimensional VAS.

0.57