The minimum consistent DFA problem cannot be approximated within any polynomial

DOI10.1145/138027.138042zbMath0774.68084OpenAlexW2074010768MaRDI QIDQ4033836

Leonard Pitt, Manfred K. Warmuth

Publication date: 16 May 1993

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/138027.138042

zbMATH Keywords

decision problemsapproximation algorithmscomputations on discrete structuresnonapproximabilityreducibility and completenessminimization of finite state machines

Mathematics Subject Classification ID

Related Items (27)

On the hardness of approximating the minimum consistent OBDD problem ⋮ Inferring a tree from walks ⋮ Minimizing nfa's and regular expressions ⋮ Efficient learning of typical finite automata from random walks ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ On the geometric separability of Boolean functions ⋮ Minimal consistent DFA from sample strings ⋮ Learning Weighted Automata ⋮ Recent advances of grammatical inference ⋮ Grammatical inference: An old and new paradigm ⋮ Learning from positive and negative examples: new proof for binary alphabets ⋮ Unnamed Item ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Kernel methods for learning languages ⋮ On the necessity of Occam algorithms ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Incremental learning of context free grammars based on bottom-up parsing and search ⋮ Inference of regular languages using state merging algorithms with search ⋮ Uniquely decodable \(n\)-gram embeddings ⋮ Learning local transductions is hard ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Prediction-preserving reducibility ⋮ Learning a Random DFA from Uniform Strings and State Information ⋮ Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference ⋮ Diameter and stationary distribution of random \(r\)-out digraphs ⋮ On the hardness of approximating the minimum consistent acyclic DFA and decision diagram. ⋮ 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