Journal of the ACM Bibliography
Leonard Pitt and Manfred K. Warmuth. The
minimum consistent DFA problem cannot be approximated within any
polynomial. Journal of the ACM, 40(1):95-142, January 1993.
[BibTeX entry]
Selected papers that cite this one
- Francesco Bergadano and Stefano Varricchio. Learning
behaviors of automata from multiplicity and equivalence queries.
SIAM Journal on Computing, 25(6):1268-1280, December 1996.
- Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E.
Schapire, and Linda Sellie. Efficient learning of typical
finite automata from random walks. Information and
Computation, 138(1):23-48, 10 October 1997.
- Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and
its connection to learning and approximation. In 37th Annual
Symposium on Foundations of Computer Science, pages 339-348,
Burlington, Vermont, 14-16 October 1996. IEEE.
- Oded Maler and Amir Pnueli. On the learnability of infinitary
regular sets. Information and Computation,
118(2):316-326, 1 May 1995.
- Osamu Maruyama and Satoru Miyano. Inferring a tree from
walks. Theoretical Computer Science, 161(1-2):289-300,
15 July 1996.
- Ronald L. Rivest and Robert E. Schapire. Diversity-based inference of finite
automata. Journal of the ACM, 41(3):555-589, May 1994.
- Ronald L. Rivest and Robert E. Schapire. Inference of finite automata using
homing sequences. Information and Computation,
103(2):299-347, April 1993.
- Ronald L. Rivest and Robert Sloan. A formal model of hierarchical
concept learning. Information and Computation,
114(1):88-114, October 1994.
- Shinichi Shimozono, Kouichi Hirata, and Ayumi Shinohara. On the hardness of
approximating the minimum consistent acyclic DFA and decision
diagram. Information Processing Letters, 66(4):165-170,
29 May 1998.
Selected references
- Dana Angluin. Learning
regular sets from queries and counterexamples. Information and
Computation, 75(2):87-106, November 1987.
- Dana Angluin. On the
complexity of minimum inference of regular sets. Information
and Control, 39(3):337-350, December 1978.
- M. R. Garey and D. S. Johnson. The complexity of near-optimal graph
coloring. Journal of the ACM, 23(1):43-49, January
1976.
- E. Mark Gold. Complexity of
automaton identification from given data. Information and
Control, 37(3):302-320, June 1978.
- David Haussler, Michael Kearns, Nick Littlestone, and Manfred K.
Warmuth. Equivalence
of models for polynomial learnability. Information and
Computation, 95(2):129-161, December 1991.
- Michael Kearns and Leslie G. Valiant. Cryptographic limitations
on learning Boolean formulae and finite automata. In
Proceedings of the Twenty First Annual ACM Symposium on Theory of
Computing, pages 433-444, Seattle, Washington, 15-17 May 1989.
- Alessandro Panconesi and Desh Ranjan. Quantifiers and
approximation (extended abstract). In Proceedings of the
Twenty Second Annual ACM Symposium on Theory of Computing, pages
446-456, Baltimore, Maryland, 14-16 May 1990.
- Christos H. Papadimitriou and Mihalis Yannakakis. Optimization,
approximation, and complexity classes (extended abstract). In
Proceedings of the Twentieth Annual ACM Symposium on Theory of
Computing, pages 229-234, Chicago, Illinois, 2-4 May 1988.
- Leonard Pitt and Leslie G. Valiant. Computational limitations on learning
from examples. Journal of the ACM, 35(4):965-984,
October 1988.
- Thomas J. Schaefer. The complexity of
satisfiability problems. In Conference Record of the Tenth
Annual ACM Symposium on Theory of Computing, pages 216-226, San
Diego, California, 1-3 May 1978.
Shortcuts: