Learnability of Probabilistic Automata via Oracles Authors: Omri Guttman, S.V.N. Vishwanathan, and Robert C. Williamson Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 171 - 182, Springer 2005. Abstract. Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ-distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ-distinguishability and generalize it to μp-distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class. ©Copyright 2005, Springer