Inference of regular languages using state merging algorithms with search

DOI10.1016/j.patcog.2004.03.027zbMath1101.68644WikidataQ58884048 ScholiaQ58884048MaRDI QIDQ2485087

Miguel Bugalho, Arlindo L. Oliveira

Publication date: 3 August 2005

Published in: Pattern Recognition (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.patcog.2004.03.027

zbMATH Keywords

DFA inference; Grammatical inference; Inference of regular grammars

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68Q45: Formal languages and automata

Related Items

Efficiently identifying deterministic real-time automata from labeled data, Regular inference as vertex coloring, Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT, Consistent reduction in discrete-event systems, A multi-parameter analysis of hard problems on deterministic finite automata, Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games

Cites Work

• Unnamed Item
• Learning regular sets from queries and counterexamples
• Occam's razor
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• System identification via state characterization
• Limits of exact algorithms for inference of minimum size finite state machines
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Speeding up the Synthesis of Programs from Traces
• Constructing Programs from Example Computations
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets
• Efficient algorithms for the inference of minimum size DFAs