Reference. CALF: Categorical Automata Learning Framework
Automata learning is a technique that has successfully been applied in verification, with the automaton type varying depending on the application domain. Adaptations of automata learning algorithms for increasingly complex types of automata have to be developed from scratch because there was no abstract theory offering guidelines. This makes it hard to devise such algorithms, and it obscures their correctness proofs. We introduce a simple category-theoretic formalism that provides an appropriately abstract foundation for studying automata learning. Furthermore, our framework establishes formal relations between algorithms for learning, testing, and minimization. We illustrate its generality with two examples: deterministic and weighted automata.
Cite
Cites 29 works (0 here)
External (29)
- Learning nominal automata (2016)
- Active learning for extended finite state machines (2016)
- Refactoring of legacy software using model learning and equivalence checking: an industrial experience report (2016)
- Minimal separating sequences for all pairs of states (2016)
- An abstract automata learning framework (Master's thesis) (2016)
- Foundations of active automata learning: an algorithmic perspective (2015)
- Learning regular languages via alternating automata (2015)
- Learning the language of error (2015)
- Protocol state fuzzing of TLS implementations (2015)
- Learning regular omega languages (2014)
- Automata learning: A categorical perspective (2014)
- A fresh approach to learning register automata (2013)
- Inference and analysis of formal models of botnet command and control protocols (2010)
- Angluin-style learning of NFA (2009)
- On the correspondence between conformance testing and regular inference (2005)
- Algorithms for learning finite automata from queries: A unified view (1997)
- Learning behaviors of automata from multiplicity and equivalence queries (1996)
- On the learnability of infinitary regular sets (1995)
- Selecting test sequences for partially-specified nondeterministic finite state machines (1995)
- An Introduction to Computational Learning Theory (1994)
- Testing finite-state machines: State identification and verification (1994)
- Learning regular sets from queries and counterexamples (1987)
- A note on the number of queries needed to identify regular languages (1981)
- Testing software design modeled by finite-state machines (1978)
- System identification via state characterization (1972)
- On the relevance of abstract algebra to control theory (1969)
- On effective construction of realizations from input-output descriptions (1966)
- Linear automaton transformations (1958)
- Gedanken-experiments on sequential machines (1956)