The minimum consistent DFA problem cannot be approximated within and polynomial
Data up to Jan 2025
Total Citations Per Year
Abstract
References (16)
Computers and Intractability: A Guide to the Theory of NP-Completeness
1979 • 45,565 citations
Introduction to automata theory, languages and computation
1981 • 11,042 citations
A theory of the learnable
1984 • 4,471 citations
The complexity of satisfiability problems
1978 • 1,763 citations
Occam's Razor
1987 • 1,044 citations
Complexity of automaton identification from given data
1978 • 767 citations
Computational limitations on learning from examples
1988 • 542 citations
The Complexity of Near-Optimal Graph Coloring
1976 • 314 citations
Crytographic limitations on learning Boolean formulae and finite automata
1989 • 272 citations
On the complexity of minimum inference of regular sets
1978 • 256 citations
Optimization, approximation, and complexity classes
1988 • 213 citations
Untitled
1990 • 211 citations
Equivalence of models for polynomial learnability
1988 • 76 citations
The minimum consistent DFA problem cannot be approximated within any polynomial
2003 • 46 citations
An application of the theory of computational complexity to the study of inductive inference.
1976 • 17 citations
On the learnability of finite automata
1988 • 17 citations