Inferring Symbolic Automata
From MaRDI portal
Abstract: We study the learnability of symbolic finite state automata (SFA), a model shown useful in many applications in software verification. The state-of-the-art literature on this topic follows the query learning paradigm, and so far all obtained results are positive. We provide a necessary condition for efficient learnability of SFAs in this paradigm, from which we obtain the first negative result. The main focus of our work lies in the learnability of SFAs under the paradigm of identification in the limit using polynomial time and data, and its strengthening efficient identifiability, which are concerned with the existence of a systematic set of characteristic samples from which a learner can correctly infer the target language. We provide a necessary condition for identification of SFAs in the limit using polynomial time and data, and a sufficient condition for efficient learnability of SFAs. From these conditions we derive a positive and a negative result. The performance of a learning algorithm is typically bounded as a function of the size of the representation of the target language. Since SFAs, in general, do not have a canonical form, and there are trade-offs between the complexity of the predicates on the transitions and the number of transitions, we start by defining size measures for SFAs. We revisit the complexity of procedures on SFAs and analyze them according to these measures, paying attention to the special forms of SFAs: normalized SFAs and neat SFAs, as well as to SFAs over a monotonic effective Boolean algebra. This is an extended version of the paper with the same title published in CSL'22.
Recommendations
Cites work
- A generic algorithm for learning symbolic automata from membership queries
- A note on the number of queries needed to identify regular languages
- Abstract symbolic automata: mixed syntactic/semantic similarity analysis of executables
- An Evaluation of Automata Algorithms for String Analysis
- Assume, guarantee or repair
- Automata learning with automated alphabet abstraction refinement
- Characteristic sets for polynomial grammatical inference
- Complexity of automaton identification from given data
- Event-clock automata: a determinizable class of timed automata
- Exact Learning of Discretized Geometric Concepts
- Fundamental Approaches to Software Engineering
- Graph-Based Algorithms for Boolean Function Manipulation
- scientific article; zbMATH DE number 5585443 (Why is no real title available?)
- Inferring regular languages and \(\omega\)-languages
- Inferring symbolic automata
- Learning Behaviors of Automata from Multiplicity and Equivalence Queries
- Learning boxes in high dimension
- Learning context-free grammars from structural data in polynomial time
- Learning I/O automata
- Learning of event-recording automata
- Learning of Structurally Unambiguous Probabilistic Grammars
- Learning regular omega languages
- Learning regular sets from queries and counterexamples
- Learning symbolic automata
- Learning the language of software errors
- Learning to divide and conquer: applying the \(L^*\) algorithm to automate assume-guarantee reasoning
- Learning unions of high-dimensional boxes over the reals
- Linear Automaton Transformations
- Minimization of symbolic automata
- Minimization of symbolic tree automata
- On the learnability of infinitary regular sets
- Queries and concept learning
- Query learning algorithm for residual symbolic finite automata
- Query learning of bounded-width OBDDs
- Symbolic solving of extended regular expression inequalities
- Teaching a smarter learner.
- The learnability of symbolic automata
- Variable automata over infinite alphabets
Cited in
(14)- Automata techniques for query inference machines
- A symbolic decision procedure for symbolic alternating finite automata
- SMT-based generation of symbolic automata
- Sigma*
- On the Inference of Finite State Automata from Positive and Negative Data
- scientific article; zbMATH DE number 4166870 (Why is no real title available?)
- scientific article; zbMATH DE number 6991602 (Why is no real title available?)
- Query learning algorithm for residual symbolic finite automata
- Improving Symbolic Automata Learning with Concolic Execution
- Inferring symbolic automata
- Passive learning of regular data languages in polynomial time and data
- Variable automata over infinite alphabets
- Constructing concise characteristic samples for acceptors of omega regular languages
- Active learning of symbolic mealy automata
This page was built for publication: Inferring Symbolic Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135753)
