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.
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.