The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial

Leonard Pitt Manfred K. Warmuth

Published in: STOC (1989)

Keyphrases

image processing
linear combination
deterministic finite automata
databases
knowledge base
clustering algorithm
lower bound
cost function
probabilistic model
simple examples