Generalized Factors of Words

Article type: Research Article

Authors: Ilie, Lucian

Affiliations: Turku Centre for Computer Science TUCS, FIN-20520 Turku, Finland

Note: [] Research supported by the Academy of Finland, Project 137358 On leave of absence from Faculty of Mathematics, University of Bucharest, Str. Academiei 14, R-70109, Bucharest, Romania

Abstract: We introduce and study relations on words which generalize the factor relation, being restrictions of the subword relation. We give an equivalent condition for the finite basis property for these relations which generalizes the well-known theorem of Higman. Some language-theoretic gaps for infinite antichains are also presented.

DOI: 10.3233/FI-1998-33302

Journal: Fundamenta Informaticae, vol. 33, no. 3, pp. 239-247, 1998