×

A one-sided Zimin construction. (English) Zbl 0969.68120

Summary: A string is Abelian square-free if it contains no Abelian squares; that is, adjacent substrings which are permutations of each other. An Abelian square-free string is maximal if it cannot be extended to the left or right by concatenating alphabet symbols without introducing an Abelian square. We construct Abelian square-free finite strings which are maximal by modifying a construction of Zimin. The new construction produces maximal strings whose length as a function of alphabet size is much shorter than that in the construction described by Zimin.

MSC:

68R15 Combinatorics on words
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: EuDML EMIS