Abstract
Traditional algorithms for learning regular languages, such as $L^*$, focus on producing Deterministic Finite Automata (DFAs). While effective, DFAs can suffer from state explosion when representing complex languages. This paper introduces a generalized framework, $XL^*$, extending learning capabilities to Universal ($UL^*$) and Alternating ($AL^*$) automata. By exploiting the succinctness of alternating representations—which can be doubly-exponentially smaller than DFAs—the proposed $AL^*$ algorithm enables the learning of complex regular languages with significantly fewer states and, in many cases, reduced query overhead.
Introduction
Regular languages are fundamental to computer science, underpinning technologies from lexical analysis to formal verification. The $L^*$ algorithm has long been the standard for active learning of these languages through membership and equivalence queries. However, the resulting DFAs are often prohibitively large. While nondeterministic models (NFAs) offer more compact representations, learning them has proven difficult due to the lack of a simple "residuality" property. This work addresses the challenge of learning even more succinct models: Alternating Finite Automata (AFAs), which combine existential and universal branching to achieve massive state reduction.
The $XL^*$ Learning Framework
The authors propose the $XL^*$ scheme, a unified approach for learning various classes of automata. Central to this framework is the definition of Residual Alternating Automata (ARFA). Unlike standard AFAs, ARFAs ensure that every state corresponds to a residual of the target language, preserving the mathematical structure needed for efficient learning while maintaining the succinctness of general AFAs.
To construct an AFA, the algorithm maintains an observation table and identifies a "monotone basis"—a set of rows that can represent all other table entries through positive Boolean combinations (AND/OR). Because finding the minimal basis is NP-hard, a greedy polynomial-time approximation is employed. The learning process iteratively refines this basis using counterexamples from equivalence queries until a correct hypothesis is reached.
Experimental Evaluation
The $XL^*$ algorithms were benchmarked against synthetic targets, including random DFAs, NFAs, UFAs, and AFAs. The results highlight a clear trade-off between model succinctness and query efficiency.
As shown in the figure above, for certain classes of targets, such as simple DFAs, the overhead of managing more complex state transitions in $NL^*$ or $AL^*$ leads to a higher number of membership queries compared to the baseline $L^*$. This confirms that the classic $L^*$ remains the optimal choice for simple, non-compressible languages.
Conversely, for complex targets that allow for significant compression, the $XL^*$ approach demonstrates its power. In these cases, the succinctness of the nondeterministic or alternating representation leads to a drastic reduction in query effort, as the algorithm operates on a much smaller state space. This efficiency is particularly pronounced for languages that are naturally existential or universal in nature.
Key Insights
- The Power of Alternation: AFAs can be doubly-exponentially smaller than DFAs. $AL^*$ successfully leverages this to learn languages that would be intractable for $L^*$.
- Matching Algorithm to Nature: $NL^*$ is best suited for "existential" languages (unions), $UL^*$ for "universal" languages (intersections), and $AL^*$ serves as a robust generalist.
- Succinctness vs. Effort: While $AL^*$ reduces the number of states and often membership queries, the complexity of finding the monotone basis and the difficulty of equivalence queries represent a significant computational trade-off.
Conclusion
This work provides a theoretical and practical foundation for learning alternating automata. By extending the $L^*$ paradigm to ARFAs, the authors have opened new avenues for representing and learning complex formal languages efficiently. Future research will explore the inclusion of negation to learn full Boolean automata and investigate methods to mitigate the NP-hardness of finding optimal monotone bases.
Summary updated