Inductive Inference Complexity

[Angluin, 1978]

D. Angluin. On the complexity of minimum inference of regular sets. Information and Control, 39:337-350, 1978.

[Angluin, 1981]

D. Angluin. A note on the number of queries needed to identify regular languages. Information and Control, 51:76-87, 1981.

[Gold, 1978]

E.M. Gold. Complexity of automaton identification from given data. Information and Control, 37:302-320, 1978.

[Haussler et al., 1994]

D. Haussler, M. Kearns, and R. Schapire. Bounds on the sample complexity of bayesian learning using information theory and the VC dimension. Machine Leraning, pages 83-113, 1994.

[Kearns and Valiant, 1989]

M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. In 21st ACM Symposium on Theory of Computing, pages 433-444, 1989.

[Pitt and Warmuth, 1988]

L. Pitt and M. Warmuth. Reductions among prediction problems: On the difficulty of predicting automata. In 3rd Conference on Structure in Complexity Theory, pages 60-69, 1988.

[Pitt and Warmuth, 1989a]

L. Pitt and M. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. Technical Report UIUCDCS-R-89-1499, University of Illinois, 1989.

[Pitt and Warmuth, 1989b]

L. Pitt and M. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. In 21st ACM Symposium on Theory of Computing, pages 421-432, 1989.

[Pitt and Warmuth, 1993]

L. Pitt and M. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. Journal of the Assocation for Computing Machinery, 40(1):95-142, 1993.

[Pitt, 1989]

L. Pitt. Inductive inference, DFA's, and computational complexity. In K.P. Jantke, editor, Analogical and Inductive Inference, number 397 in Lecture Notes in Artificial Intelligence, pages 18-44. Springer-Verlag, Berlin, 1989.

[Yokomori, 1995]

T. Yokomori. On polynomial-time learnability in the limit of strictly deterministic automata. Machine Learning, 19:153-179, 1995.