Learning Probabilistic Languages by k-Testable Machines

International Symposium on Theoretical Aspects of Software Engineering (TASE), pp. 129–136

Abstract

A k-testable machine is a finite automaton which recognizes a language L by only seeing a window of size k of each string in L. In this paper we use k-testable machines to recognize probabilistic languages and propose a novel algorithm to learn them. We work in the context of passive learning as our algorithm is based on a finite sample of strings belonging to the target language equipped with frequencies. Because our algorithm learns a probabilistic automaton, the resulting language is less sensitive to noise threshold than García's algorithm. When compared with the ALERGIA learning algorithm, our method provides a better result in the case of the target language being a k-testable language. In fact, in this case, for the given window k we can learn at the limit the target language exactly.

Authors 2

1. Wenjing Chu Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Netherlands

2. Marcello Bonsangue Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, Netherlands