The minimum consistent DFA problem cannot be approximated within any polynomial

approximation algorithms decision problems computations on discrete structures nonapproximability reducibility and completeness minimization of finite state machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
Minimizing nfa's and regular expressions
STACS 2005
Minimal consistent DFA from sample strings
Minimal consistent DFA revisited

Cited in

(32)

Prediction-preserving reducibility
Uniquely decodable n-gram embeddings
Approximate learning of limit-average automata
Learning a Random DFA from Uniform Strings and State Information
Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
On approximating non-regular languages by regular languages
Minimal consistent DFA revisited
On the hardness of approximating the minimum consistent OBDD problem
Inferring a tree from walks
Regular inference as vertex coloring
Learning weighted automata
On the equivalence of Occam algorithms
Learning from positive and negative examples: new proof for binary alphabets
On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
Recent advances of grammatical inference
Kernel methods for learning languages
On the necessity of Occam algorithms
Inference of regular languages using state merging algorithms with search
A multi-parameter analysis of hard problems on deterministic finite automata
Minimizing nfa's and regular expressions
Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Grammatical inference: An old and new paradigm
Learning local transductions is hard
Diameter and stationary distribution of random r-out digraphs
On the geometric separability of Boolean functions
Minimal consistent DFA from sample strings
Parallel algorithms for minimal nondeterministic finite automata inference
Learning from positive and negative examples: dichotomies and parameterized algorithms
FlexFringe: modeling software behavior by learning probabilistic automata
Efficient learning of typical finite automata from random walks
Incremental learning of context free grammars based on bottom-up parsing and search
A survey of opponent modeling in adversarial domains

This page was built for publication: The minimum consistent DFA problem cannot be approximated within any polynomial

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