The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial

Leonard Pitt, Manfred K. WarmuthJ. ACM 1993 · DOI

BibTeX
@article{pitt1993minimum,
  author = {Leonard Pitt and Manfred K. Warmuth},
  title = {{The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial}},
  journal = {J. ACM},
  year = {1993},
  doi = {10.1145/138027.138042},
}

Loading related content...

Figure