Learning Probabilistic Automata and Markov Chains via Queries

Angluin, D. (1978). On the complexity of minimum inference of regular sets. Information and Control, 39, 337–350. Angluin, D. (1981). A note on the number of queries needed to identify regular languages. Information and Control, 51, 76–87. Angluin, D. (1987a). Queries and concept learning. Machine Learning, 2, 319–342. Angluin, D. (1987b). Learning regular sets from queries and counterexamples. Information and Control, 75, 87–106. Angluin, D. (1987c). Learning k-term DNF formulas using queries and counterexamples (Technical Report YALEU/DCS/RR-559). New Haven, CT: Yale University, Computer Science Department. Angluin, D. (1988). Negative results for equivalence queries (Technical Report YALEU/DCS/RR-648). New Haven, CT: Yale University, Computer Science Department. Angluin, D. (1989). Equivalence queries and approximate fingerprints. Proceedings of the Second Workshop on Computational Learning Theory (pp. 134–145). San Mateo, CA: Morgan Kaufmann. Angluin, D., Hellerstein, L., & Karpinski, M. (1989). Learning read-once formulas with queries (Technical Report UCB/CSD 89-528). Berkeley, CA: University of California-Berkeley, Computer Science Division (EECS). Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36, 929–965. Board, R., & Pitt, L. (1990). On the necessity of Occam algorithms. Proceedings of the Twenty-Second Annual Symposium on Theory of Computing (pp. 54–63). New York: NY: ACM Press. Bush, R.R., & Mosteller, F. (1955). Stochastic models for learning. New York, NY: Wiley. DeSantis, A., Markowsky, G., Wegman, M.N. (1988). Learning probabilistic prediction functions, Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science (pp. 110–119). Los Alamitos, CA: IEEE Press. Fu, K.S. (1966). Stochastic automata as models of learning systems. Proceedings of Symposium on Computer and Information Science. Columbus, OH: Purdue University. Gold, E.M. (1978). Complexity of automaton identification from given data. Information and Control, 37, 302–320. Haussler, D., Kearns, M., Littlestone, M., & Warmuth, M.K. (1988). Equivalence of models for polynomial learnability. Proceedings of the First Workshop on Computational Learning Theory (pp. 42–55). San mateo, CA: Morgan Kaufmann. Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4, 373–395. Kearns, M., Li, M., Pitt, L., & Valiant, L.G. (1987). On the learnability of boolean formulae. Proceedings of the Nineteenth Annual Symposium on Theory of Computing (pp. 285–295). New York, NY: ACM Press. Kearns, M., & Valiant, L.G. (1989). Cryptographic limitations on learning Boolean formulae and finite automata. Proceedings of the Twenty-First Annual Symposium on Theory of Computing (pp. 433–444). New York, NY: ACM Press. Khachiyan, L.G. (1979). A polynomial algorithm in linear programming (in Russian). Translated in Soviet Mathematics Doklady, 20, 191–194. Paz, A. (1971) Introduction to probabilistic automata. New York, NY: Academic Press. Pitt, L., (1989). Inductive inference, DFAs, and computational complexity (Technical Report UIUCDCS-R-89-1530). Champaign, IL: Univeristy of Illinois at Urbana-Champaign, Department of Computer Science. Pitt, L., & Warmuth, M.K. (1989). The minimum consistent DFA problem cannot be approximated within any polynomial. Proceedings of the Twenty-First Annual Symposium on theory of Computing (pp. 421–432). New York, NY: ACM Press. Pitt, L., & Warmuth, M.K. (1990). Prediction-preserving reducibility. Journal of Computer and System Sciences, 43, 430–467. Rabin, M.O. (1963). Probabilistic automata. Information and Control, 6, 230–245. Rudich, S. (1985). Inferring the structure of a Markov chain from its output. Proceedings of the Twenty-Sixth Annual Symposium on Foundations of Computer Science (1989) (pp. 321–326). Los Alamitos, CA: IEEE Press. Tzeng, W. (1990). A polynomial-time algorithm for the equivalence of probabilistic automata. Submitted for publication. Valiant, L.G. (1984). A theory of the learnable. Communications of the Association for Computing Machinery, 27, 1134–1142.