Efficient algorithms for the inference of minimum size DFAs

DOI10.1023/A:1010828029885MaRDI QIDQ5945683zbMATH OpenWikidataFDO

Authors Arlindo L. Oliveira, João P. M. Silva

Publication date 21 April 2002

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1010828029885

zbMATH Keywords

minimum size deterministic automata

Mathematics Subject Classification ID

Searching and sorting (68P10) Formal languages and automata (68Q45)

Recommendations

• Efficient minimization of DFAs with partial transition
• Incremental DFA minimisation
• Incremental DFA minimisation
• Fast brief practical DFA minimization
• Description and analysis of a bottom-up DFA minimization algorithm
• Limits of exact algorithms for inference of minimum size finite state machines
• Computing minimal separating DFAs and regular invariants using SAT and SMT solvers
• Weak minimization of DFA -- an algorithm and applications
• Weak Minimization of DFA — An Algorithm and Applications
• A new algorithm for the construction of minimal acyclic DFAs.

Cited in

(24)

• A new algorithm for the construction of minimal acyclic DFAs.
• Inferring regular languages and \(\omega\)-languages
• Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
• Oblivious DFA evaluation on joint input and its applications
• FSM inference from long traces
• Certifying DFA bounds for recognition and separation
• Minimal consistent DFA from sample strings
• A multi-parameter analysis of hard problems on deterministic finite automata
• Efficient symmetry breaking for SAT-based minimum DFA inference
• LARS: a learning algorithm for rewriting systems
• Inference of regular languages using state merging algorithms with search
• Active coevolutionary learning of deterministic finite automata
• Learning Meets Verification
• Limits of exact algorithms for inference of minimum size finite state machines
• Weak Minimization of DFA — An Algorithm and Applications
• An optimally data efficient isomorphism inference algorithm
• Regular inference as vertex coloring
• Parallel algorithms for minimal nondeterministic finite automata inference
• Finding All Minimum-Size DFA Consistent with Given Examples: SAT-Based Approach
• Some New Features and Algorithms for the Study of DFA
• Grammatical Inference: Algorithms and Applications
• Learning Minimal DFA: Taking Inspiration from RPNI to Improve SAT Approach
• Report on the exact methods for finding minimum-sized DFA
• Unsupervised automata learning via discrete optimization

This page was built for publication: Efficient algorithms for the inference of minimum size DFAs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5945683)