Inference of regular languages using state merging algorithms with search

DOI10.1016/J.PATCOG.2004.03.027zbMATH Open1101.68644OpenAlexW2015033692WikidataQ58884048 ScholiaQ58884048MaRDI QIDQ2485087FDOQ2485087

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

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

zbMATH Keywords

Grammatical inferenceDFA inferenceInference of regular grammars

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)