Learning Unions of k-Testable Languages
Preprint
Abstract
A classical problem in grammatical inference is to identify a language from a set of examples. In this paper, we address the problem of identifying a union of languages from examples that belong to several different unknown languages. Indeed, decomposing a language into smaller pieces that are easier to represent should make learning easier than aiming for a too generalized language. In particular, we consider k-testable languages in the strict sense (k-TSS). These are defined by a set of allowed prefixes, infixes (sub-strings) and suffixes that words in the language may contain. We establish a Galois connection between the lattice of all languages over alphabet {\Sigma}, and the lattice of k-TSS languages over {\Sigma}. We also define a simple metric on k-TSS languages. The Galois connection and the metric allow us to derive an efficient algorithm to learn the union of k-TSS languages. We evaluate our algorithm on an industrial dataset and thus demonstrate the relevance of our approach.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Aural Pattern Recognition Experiments and the Subregular HierarchyJournal of Logic, Language and Information, 2011
- Sequences Classification by Least General GeneralisationsLecture Notes in Computer Science, 2010
- k-TSS language models in speech recognition systemsComputer Speech & Language, 2001
- Principles of Program Analysis1999
- Learning local languages and their application to DNA sequence analysisIEEE Transactions on Pattern Analysis and Machine Intelligence, 1998
- Inference of k-testable languages in the strict sense and application to syntactic pattern recognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990