Accepted papers
- and
Automata Learning for Probabilistic IO Automata with Continuous Outputs
Passive automata learning is a machine learning technique that infers an automaton model of system from a set of execution traces. While originally conceived for inferring deterministic finite automata, many algorithms for different formalisms have since been developed, targeting systems with infinite state space as well as stochastic systems. However, the combined setting of stochastic reactive systems with continuous output domains is currently under explored.
For such systems, existing work typically applies classical methods on discretized data. In this paper, we present a method for lifting such models back to the continuous domain. The main contribution is a novel automata learning method that takes the continuous data into account during the inference process. This reduces the impact of the discretization method on the quality of the resulting models. We evaluate the approach by comparing it to established algorithms that operate exclusively on discretized data. - , and
A formal approach for understanding the behavior of constrained language models
We study language models under explicit formal constraints by treating common operations, such as prompting, masking, temperature scaling, and vocabulary translation, as composable transformations, in particular those that preserve the set of generable sequences and/or its probability distribution.
We focus on constraints that disable tokens, potentially leading to dead-ends during generation. Moreover, we formalize bounded-length and safe decoding procedures.
The theoretical results enable the algorithmic approximation of the probability of subsets (properties) of the generable language, as well as active learning of automata representations, such as DFA o Moore machines.
We evaluate the approach to analyze the behavior of several state-of-the-art large language models. - , , , and
The Long and Short of It: An experimental investigation into the role of shorter strings in learning regular languages
We test the performance of state merging algorithms against four neural network architectures on MLRegTest, a benchmark for learning regular languages from positive and negative data (van der Poel et al., 2024). Prior work by Soubki and Heinz (2023) on a preliminary version of MLRegTest found that neural learning models generally outperformed state merging algorithms on this benchmark. However, Soubki and Heinz (2023) also note that MLRegTest excludes strings shorter than length 20 and report a follow-up experiment demonstrating that the addition of shorter strings dramatically improves the performance of state merging algorithms. They did not examine the performance of neural models with shorter strings.
We expand on this work by conducting several experiments using the published version of MLRegTest. Firstly, we conduct a gridsearch over the hyperparameters provided by the FlexFringe software to identify the bestperforming state merging system. We then report the results of this state merging algorithm on experimental setups which vary by training set size, inclusion of shorter training strings, and inclusion of intermediate-length training strings. We also subject the neural baselines from van der Poel et al. (2024) to these same experiments, and compare the performance between these and the state merging algorithm.
We conclude that the gated recurrent unit has the strongest performance across the benchmarks, with some interesting caveats. Namely, the state merging algorithm outperforms all neural architectures on regular languages which count modulo some positive integer. Additionally, the state merging algorithm sees much greater improvement and more resiliency to adversarial test sets from the inclusion of shorter strings, while the neural models do much better with longer strings and larger data samples. These results suggest that state merging approaches may be more attuned to learning from shorter, smaller input data, while neural learners need the opposite. - and
Compositional Learning of Mealy Machines with Projections
We consider parallel composition in the context of active automata learning. The problem we solve is that automata learning typically learns a single nite state machine for a system, even when the system is composed of smaller subsystems. We assume a closed-box setting, where the compositional structure of the system is not known and has to be inferred during learning. We develop a new algorithm, CoALP, which, like L* or TTT, learns the system but simultaneously learns a decomposition of the system. Depending on the structure of the system, this reduces the number of queries drastically, as shown by an evaluation of the algorithm. The algorithm CoALP is generic in the sense that it can use any learning algorithm for the subsystems. - , , and
Concise One-Layer Transformers Can Perform Dictionary Lookup
While transformers have proven enormously successful in a range of tasks, their fundamental properties as models of computation are not well understood. This paper contributes to the study of the expressive capacity of transformers, focusing on their ability to perform the fundamental computational task of looking up a key in a dictionary. We prove that concise 1-layer transformers (i.e., with a polylog bound on the product of the number of heads, the embedding dimension, and precision) are capable of doing this task when the key and value are represented in the same position of the input, but not when the keys and values are encoded in different input positions. Concise 2-layer transformers can perform the task in the second case. Experimentally, we find an alignment between what we have proven can be computed by concise transformers and what can be practically learned. title: Learnability of Grammars with Finite Exceptions -
Learnability of Grammars with Finite Exceptions
Inspired by natural language phenomena, we provide a characterization of the classes of formal languages that can be learned even if their grammars include finitely many exceptions. Specifically, we consider a setup where the learner must faithfully acquire any arbitrary exceptional strings present in the input presented to them, in addition to any general patterns present. We use the identifiability in the limit framework to show that classes of languages with finitely many arbitrarily omitted strings cannot be identified except in trivial cases, while languages with finitely many arbitrarily included strings can be identified non-trivially. We then present strategies for identification of these arbitrarily augmented languages. - , and
Learning deterministic finite-state machines from the prefixes of a single string is NP-complete
It is well known that computing a minimum DFA consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines. - and
Linguistic Faithfulness Enables Decomposition Learning of Sequential Functions from Given Structure
Motivated by a learning problem in natural language phonology, this paper studies the learnability of series of sequential transductions from their composition when given a priori knowledge of their finite-state structures. Appealing to the notion of faithfulness, we propose linguistically-amenable conditions under which sequential transductions decompose uniquely into given finite-state structures. Under such conditions, we present a decomposition algorithm that enables strong in-the-limit identification of series of sequential transductions given data from their composition. -
Learning DFA with neural networks: Self-Organising Automata
We introduce a hybrid approach for inferring Deterministic Finite Automata (DFA) from examples, combining neural networks with classical grammatical inference techniques. The central intuition is that a neural network trained as a sequence acceptor implicitly encodes, in its hidden states, a continuous approximation of the state structure of the target language. Our goal is to make this structure explicit, and extract from it a discrete, interpretable automaton. The method proceeds in two stages. First, a neural network, typically a recurrent neural network (RNN), is trained as a sequence acceptor, associating each input prefix with a continuous vector representation of its processing state. Second, a dedicated neural model, which we call a Self-Organizing Automaton (SOA), is trained to map these representations to states of an inferred automaton. The training of the SOA is inspired by both Self-Organizing Maps and the RPNI state-merging algorithm, combining unsupervised topological organization with consistency-driven state identification. This combination allows us to exploit the generalization capabilities of neural models while ultimately producing an explicit and interpretable automaton, rather than a purely black-box predictor. -
The Pumping Inference Algorithm: Exploiting the Pumping Lemma for CFGs to Learn PCFGs
The probabilistic grammar inference is a problem that, given an input string dataset, aims to find a rule set and its probabilities that better produce it. It is applied in Bioinformatics, Computer Music, Computational Linguistics, Architecture, and Software Engineering, to name a few. Developing grammar learning methods from a dataset is crucial and can benefit all these research areas. For probabilistic context-free grammar (PCFG) inference, we noticed the lack of algorithms capable of finding context-free grammar structures with only positive data, which is probably an undecidable problem. Hence, researchers choose to use probability estimation algorithms to learn it. This paper proposes a new algorithm based on the pumping lemma for Context-Free Languages. This algorithm learns grammar’s structure and achieves lower prediction accuracy averages than the Gibbs Sampling algorithm in learning the Dyck-n languages and in the languages with ∥a∥ = ∥b∥ and ∥2a∥ = ∥b∥. -
Simulation Reductions for the Complexity of Subsequential Transducer Identification from Non-Characteristic Data
This paper proposes a strategy for proving the computational hardness of finite-state transducer identification problems. Although it is well known that identifying classes of transductions characterized by state-counting bounds is NP-complete, the case of identifying structured classes of subsequential transductions is less understood, despite its relevance to current in-the-limit learning algorithms like SOSFIA. In this paper, we apply the proposed strategy to prove that both previous identification problems are NP-complete. This provides a simpler proof of the known result, as well as a new hardness bound on the identification of subsequential transducers when given a priori structural information in the sense of SOSFIA. - , , , and
A Minimum Description Length Approach to Grammar Inference in Neural Networks
Accurate generalization to symbolic grammars from realistic amounts of data lies at the heart of many reasoning tasks. Yet it remains a challenge for state-of-the-art neural networks, even when the architecture is known to be expressive enough to represent the target grammar.
Using a variety of formal language tasks we show that the choice of regularization method plays a crucial role: when trained on formal languages with standard regularization (L_1, L_2, or none), expressive RNN architectures not only fail to converge to correct solutions but are actively pushed away from perfect initializations. In contrast, applying the Minimum Description Length (MDL) principle to balance model complexity with data fit provides a theoretically grounded regularization method. Using MDL, perfect solutions are selected over approximations, independently of the optimization algorithm. We propose that unlike existing regularization techniques, MDL introduces the appropriate inductive bias for grammar inference, which effectively counteracts overfitting and promotes generalization. - and
Identification in the Limit with Polynomial Time and Data of (k,l)-Local-Context Substitutable Grammars
Clark and Eyraud (2007) introduced the class of substitutable languages and showed that context-free substitutable languages are identifiable in polynomial time in the limit from positive data. Yoshinaka (2008) generalized this result to (k, l)-substitutable context-free languages, and Coste et al. (2012) extended it to (k, l)-local substitutable context-free languages. However, these classes are only learnable under a polynomial thick-data relaxation of the Identifiable in the Limit with Polynomial Time and Data (IPTD) criterion.
In this paper, we introduce a class of grammars providing a canonical representation of(k, l)-local-context substitutable languages, which combine (k, l)-substitutability and (k, l)-local substitutability, together with a linear-time inference algorithm. This allows us to prove that this class is IPTD, yielding the first IPTD result for a class of substitutable languages without thickness assumptions - and
Learning Bimachines from Aligned Examples
Bimachines provide a deterministic representation of functional string transductions by combining a left-to-right DFA, a right-to-left DFA, and a local output function depending on both contexts. We study the aligned learning regime in which each training example provides one output chunk per input position.
In this setting we present a practical bimachine learner based on RPNI-style state merging: it starts from left and right prefix-tree automata, constructs a partial local output table from aligned chunks, alternates merge-and-fold passes on the two sides, validates merges against training constraints and witness queries, and finally minimizes the resulting bimachine after optional output-table completion.
The learner supports deletions and anchored insertions without input-ε moves. Experiments on a battery of local, global, and length-changing synthetic transductions recover compact bimachines with perfect oracle agreement in the aligned-oracle setting. In a separate sample-only regime on randomly generated target bimachines, held-out agreement improves predictably with more aligned examples and with smaller target machines, while exact structural recovery emerges first on the smallest families.