Inference of regular languages using state merging algorithms with search

DOI10.1016/J.PATCOG.2004.03.027MaRDI QIDQ2485087zbMATH OpenOpenAlexWikidataFDO

Authors 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

Grammatical inferenceDFA inferenceInference of regular grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Recommendations

• State-Merging DFA Induction Algorithms with Mandatory Merge Constraints
• Grammatical Inference: Algorithms and Applications
• scientific article; zbMATH DE number 2085402
• Learning Regular Languages Using Nondeterministic Finite Automata
• scientific article; zbMATH DE number 2019601

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• Complexity of automaton identification from given data
• Constructing Programs from Example Computations
• Efficient algorithms for the inference of minimum size DFAs
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• Learning regular sets from queries and counterexamples
• Limits of exact algorithms for inference of minimum size finite state machines
• Occam's razor
• On the complexity of minimum inference of regular sets
• Speeding up the Synthesis of Programs from Traces
• System identification via state characterization
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(11)

• Regular inference as vertex coloring
• Synthesis of quantifier-free DNF sentences from inconsistent samples of strings with EF games and SAT
• An approach to the inference of finite state machines based on a gravitationally-inspired search algorithm
• Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
• State-Merging DFA Induction Algorithms with Mandatory Merge Constraints
• Efficiently identifying deterministic real-time automata from labeled data
• Improvement of the state merging rule on noisy data in probabilistic grammatical inference.
• Grammatical Inference: Algorithms and Applications
• scientific article; zbMATH DE number 2019593 (Why is no real title available?)
• Consistent reduction in discrete-event systems
• A multi-parameter analysis of hard problems on deterministic finite automata

This page was built for publication: Inference of regular languages using state merging algorithms with search

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