{PAC}-learnability of Probabilistic Deterministic Finite State Automata


Authors

Clark, Alexander and Thollard, Franck

Year

2004

Abstract

We study the learnability of Probabilistic Deterministic Finite State Automata under a modified PAC-learning criterion. We argue that it is necessary to add additional parameters to the samplecomplexity polynomial, namely a bound on the expected length of strings generated from any state,and a bound on the distinguishability between states. With this, we demonstrate that the class of PDFAs is PAC-learnable using a variant of a standard state-merging algorithm and the Kullback-Leibler divergence as error function.

link

local copy of pdf

citation in bibtex

comments powered by Disqus