A one-sided Zimin construction (Q5940667)
From MaRDI portal
scientific article; zbMATH DE number 1633285
Language | Label | Description | Also known as |
---|---|---|---|
English | A one-sided Zimin construction |
scientific article; zbMATH DE number 1633285 |
Statements
A one-sided Zimin construction (English)
0 references
13 August 2001
0 references
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.
0 references
Abelian square-free string
0 references