CS Paper Radar

Leveraging Restrictions to Optimize Register Automata Learning

Paul Fiterau-Brostean, Bengt Jonsson, Konstantinos Sagonas, Fredrik Tåquist

cs.FL ·submitted 2026-11-18 21:09 UTC · v1
publishedhot direction

Abstract

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.

Comment
36 pages, 6 figures, to appear in VMCAI 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Learning Canonical Register Automata over Ordered Data Domains

cs.CL cs.LG ·2026-08-19 ·Yong Li, Qiyi Tang, Di-De Yen
similarity 0.70
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

Testing and Learning Symbolic Finite State Machines

cs.FL cs.SE ·2026-09-22 ·Wen-ling Huang, Jan Peleska
theory similarity 0.64
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.

0.18

OmegaHyper: Explicit-State HyperLTL Model Checking on an omega-Automaton Diet

cs.SE cs.FL ·2026-11-18 ·Hugo Pacheco
similarity 0.63
Abstract

HyperLTL extends LTL with quantification over traces. AUtoHyper is the de facto explicit-state model checker for HyperLTL, complete for an arbitrary quantifier prefix: it eliminates quantifiers through products of the formula's omega-automaton with the systems, complementing on quantifier alternations. However, it suffers from state explosion, as it fully materializes input systems and intermediate automata. We present OmegaHyper, an overhaul of AutoHyper that keeps its algorithm but decomposes and reduces the size of the processed automata, and integrates the Kofola omega-automaton complementation tool. We compare OmegaHyper with existing explicit-state and symbolic HyperLTL model checkers, on 120 benchmarks from their published suites. OmegaHyper improves the performance of explicit-state HyperLTL model checking by up to orders of magnitude; bounded symbolic tools still reach further on violated instances with short counterexamples, as expected.

0.27

Complete Test Suites for Effectful Automata

cs.FL ·2026-11-19 ·Bálint Kocsis, Rick Koenders, Joshua Moerman, Jurriaan Rot
theory similarity 0.62
Abstract

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.

0.40

From Transformers to Weighted Automata: Towards the Verification of Large Language Models

cs.FL cs.LG ·2026-10-03 ·Smayan Agarwal, Aslah Ahmad Faizi, Shobhit Singh, Aalok Thakkar
published similarity 0.61
Abstract

Large language models (LLMs) are increasingly deployed in safety-critical settings, yet their black-box nature makes it difficult to provide formal guaranties about their behavior. Existing verification approaches rely primarily on empirical probing and testing, leaving open the question of how to reason rigorously about general-purpose trans- former architectures. In this work, we establish a principled bridge between transformers and weighted automata, a classical model from formal language theory. This connection enables us to transfer verification tools from automata the- ory to the analysis of LLMs. Our contributions are twofold: First, we develop a formal correspondence between transformer architectures and weighted automata over reals, showing how distributional properties of LLMs can be captured within this framework. Second, we introduce an identity testing algorithm for weighted automata that provides a statis- tical method for distinguishing whether two stochastic models define the same distribution up to a tolerance threshold. This work provides the first formal bridge between modern neural se- quence models and classical automata theory, clarifying both the poten- tial and the computational challenges for rigorous LLM verification.

0.34

Efficient Nominal Automata Computation with Strong Nominal Sets

cs.FL ·2026-11-17 ·Hiroya Fujinami
hot direction similarity 0.59
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.40

AutoAssumption: Searching over Assumptions Discovers ML-Systems Algorithms

cs.AI cs.LG ·2026-11-10 ·Igor Sadalski, Minghao Guo, Benjamin Jones, Wojciech Matusik
code/data similarity 0.58
Abstract · 52 pages (9 main + references and appendix), 14 figures, 13 tables

Many advances in ML systems came from breaking an assumption that earlier methods took for granted: speculative decoding dropped the assumption that a model needs one forward pass per token. Yet algorithms rarely state their assumptions, so experts and discovery harnesses search over programs, where one edit changes several design choices and gains are difficult to attribute. Searching over the assumptions themselves remains largely unexplored. Writing algorithms as proofs makes their assumptions explicit and turns algorithm design into a search over a small, structured space that an LLM can explore and a proof checker can audit. We formalize 89 algorithms from KV-cache eviction, weight pruning and speculative decoding as proof graphs with explicit assumptions, checked in Lean. Our harness, AutoAssumption, relaxes one assumption of a published method, re-derives and re-proves it, and generates its code. In KV-cache eviction and weight pruning, this search improved on every published algorithm we ran and produced state-of-the-art algorithms. The eviction algorithm has the highest RULER-4K score of the published methods we ran, and the pruning algorithm the lowest perplexity of thirteen on four LLaMA models. At equal budget, the harness scores within a point of OpenEvolve, an open-source implementation of AlphaEvolve, with a lower standard deviation across repeats. Future work will formalize more fields and combine them through the principal assumptions they share.

0.33

LLM-Assisted Bi-Approximate CHC Solving

cs.LO cs.AI ·2026-10-16 ·Baiting Jiang
similarity 0.57
Abstract · 22 pages, 8 figures, 5 tables

Constrained Horn clause (CHC) solvers often struggle to discover deep counterexamples whose derivations may require extensive rule unfolding. Although large language models (LLMs) can propose long-range symbolic relations, prior work on formally checked LLM-assisted verification has mainly focused on generating inductive invariants and concrete traces. We exploit this broader capability through Derivation Power Under-approximations (DPUs). Each DPU is a solver-certified under-approximation of the relation induced by a multi-step CHC derivation. An LLM proposes each DPU with symbolic intermediate-state witnesses that enable SMT validation without introducing additional quantifiers. Validated DPUs can be composed and reused soundly. Building on this mechanism, our LLM-assisted framework HornCraft combines invariant generation for over-approximation with DPU generation for under-approximation in CHC solving. On 260 linear and nonlinear integer-arithmetic CHC-COMP benchmarks left unresolved by a 30-minute Spacer run, HornCraft returns certified verdicts for 228 instances. It certifies 42 instances as unsafe, compared with 22 when DPU construction and reuse are disabled.

0.23