Learning k-testable and k-piecewise testable languages from positive data
Pedro García, José Ruiz · 2004
The families of locally testable (LT) and piecewise testable (PWT) languages have been deeply studied in formal language theory. They have in common that the role played by the segments of length k of their words in the first family is played in the second by their subwords (sequences of non necessarily consecutive symbols), also of length k. We propose algorithms that, given k>0, identify both families of languages (k-PWT and k-LT) from positive data in the limit. The first one identifies the family of k-PWT languages making use of a combinatorial property discovered by Simon and improves the complexity of a previous algorithm for that family [25]. The second algorithm identifies the family of k-LT languages using a result about the cascade product of automata. In this product, for each k, one of the factors is a fixed transducer and the second is the automaton obtained by the first algorithm for k = 1 using the transduction of the sample as input.