Inference of finite automata using homing sequences
We present new algorithms for inferring an unknown finite-state automaton from its input/output behavior, even in the absence of a means of resetting the machine to a start state. A key technique used is inference of a homing sequence for the unknown automaton. Our inference procedures experiment with the unknown machine, and from time to time require a teacher to supply counterexamples to incorrect conjectures about the structure of the unknown automaton. In this setting, we describe a learning algorithm that, with probability \(1-\delta\), outputs a correct description of the unknown machine in time polynomial in the automaton's size, the length of the longest counterexample, and \(\log (1/ \delta)\). We present an analogous algorithm that makes use of a diversity-based representation of the finite-state system. Our algorithms are the first which are provable effective for these problems, in the absence of a ``reset. We also present probabilistic algorithms for permutation automata which do not require a teacher to supply counterexamples. For inferring a permutation automaton of diversity \(D\), we improve the best previous time bound by roughly a factor of \(D^ 3/ \log D\).
- Selection of relevant features and examples in machine learning
- Efficient learning of typical finite automata from random walks
- A simple algorithm for learning O(log n)-term DNF
- Map learning with uninterpreted sensors and effectors
- Inferring regular languages and \(\omega\)-languages
- Even linear simple matrix languages: formal language properties and grammatical inference.
- Piecemeal graph exploration by a mobile robot.
- The query complexity of finding local minima in the lattice
- Learning to win process-control games watching game-masters
- The power of a pebble: Exploring and mapping directed graphs
- Learning fallible deterministic finite automata
- \(L^\ast\)-based learning of Markov decision processes (extended version)
- Generating models of infinite-state communication protocols using regular inference with abstraction
- Learning Mealy machines with one timer
- Learning Moore machines from input-output traces
- Efficient active automata learning via mutation testing
- An efficient query learning algorithm for ordered binary decision diagrams
- Learning to verify branching time properties
- Efficient unlinkable sanitizable signatures from signatures with re-randomizable keys
- Enhancing Automata Learning by Log-Based Metrics
- Inferring canonical register automata
- Learning grammars and automata with queries
- On the Inference of Finite State Automata from Positive and Negative Data
- Automata learning with automated alphabet abstraction refinement
- Compositional reasoning
- Identification of automata by sequential learning
- A novel learning algorithm for Büchi automata based on family of DFAs and classification trees
- AUTOMATED COMPOSITIONAL REASONING OF INTUITIONISTICALLY CLOSED REGULAR PROPERTIES
- The Birth of Model Checking
- Automated Compositional Reasoning of Intuitionistically Closed Regular Properties
- Grey-Box Checking
- Learning Minimal Separating DFA’s for Compositional Verification
- Learning finite cover automata from queries
- Diversity-based inference of finite automata
- Model-based learning of interaction strategies in multi-agent systems
- scientific article; zbMATH DE number 6991602 (Why is no real title available?)
- Active learning of nondeterministic finite state machines
- A succinct canonical register automaton model
- Learning register automata: from languages to program structures
- \textsc{PAutomaC}: a probabilistic automata and hidden Markov models learning competition
- Protocol state machine reverse engineering with a teaching-learning approach
- Query learning algorithm for residual symbolic finite automata
- Compositional CSP traces refinement checking
- A learning-based synthesis approach to decentralized supervisory control of discrete event systems with unknown plants
- On the Length of Homing Sequences for Nondeterministic Finite State Machines
- A Myhill-Nerode theorem for register automata and symbolic trace languages
- Learning of event-recording automata
- Regular model checking revisited
- Never-stop context-free learning
- Active model learning of stochastic reactive systems
- Compositional learning for interleaving parallel automata
- Active automata learning as black-box search and lazy partition refinement
- Learning and characterizing fully-ordered lattice automata
- A survey of model learning techniques for recurrent neural networks
- A Myhill-Nerode theorem for finite state matrix automata and finite matrix languages
- Fingerprinting and analysis of Bluetooth devices with automata learning
- Benchmarking combinations of learning and testing algorithms for active automata learning
- Reverse Engineering Through Automata Learning
- A new approach for active automata learning based on apartness
- Learning realtime one-counter automata
- Active learning of deterministic timed automata with Myhill-Nerode style characterization
- L^*-based learning of Markov decision processes
- Timed automata verification and synthesis via finite automata learning
- Active learning for sound negotiations
- Classic learning
- Guarded Kleene algebra with tests: automata learning
- An active learning algorithm for bidirectional deterministic finite automata
- Unsupervised automata learning via discrete optimization
- Timed automata verification and synthesis via finite automata learning
- Benchmarking combinations of learning and testing algorithms for automata learning
- Active learning techniques for pomset recognizers
- \(SL^{\lambda}\): a scalable algorithm for register automata learning
- Active learning for extended finite state machines
- Quantified data automata for linear data structures: a register automaton model with applications to learning invariants of programs manipulating arrays and lists
- New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries
- Inference of deterministic one-counter languages
- AutoSyn: A new approach to automated synthesis of composite web services with correctness guarantee
- On reconstruction of information on an input word in a Medvedev permutation automaton given initial and final states
- Three optimizations for assume-guarantee reasoning with \(L^{*}\)
- Learning to divide and conquer: applying the \(L^*\) algorithm to automate assume-guarantee reasoning
- Verification of evolving software via component substitutability analysis
- Automatic symbolic compositional verification by learning assumptions
This page was built for publication: Inference of finite automata using homing sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365762)
