A Lattice of Sets of Alignments Built on the Common Subwords in a Finite Language


Laurent Miclet, Nelly Barbot, Baptiste Jeudy ;
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:164-176, 2012.


We define the locally maximal subwords and locally minimal superwords common to a finite set of words. We also define the corresponding sets of alignments. We give a partial order relation between such sets of alignments, as well as two operations between them. We show that the constructed family of sets of alignments has the lattice structure. We give hints to use this structure as a machine learning basis for inducing a generalization of the set of words.

Related Material