Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure


Learning k-Testable and k-Piecewise Testable Languages from Positive Data

PEDRO GARCÍA, JOSÉ RUIZ

Abstract

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.

Download:
PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster