(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 4.2' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 166645, 5894]*) (*NotebookOutlinePosition[ 167896, 5937]*) (* CellTagsIndexPosition[ 167823, 5931]*) (*WindowFrame->Normal*) Notebook[{ Cell["\<\ New Abelian Square-Free DT0L-Languages over 4 Letters \ \>", "Subtitle", TextAlignment->Center, TextJustification->0], Cell["\<\ Veikko Ker\[ADoubleDot]nen 15 June 2002 and 15 June 2003 Rovaniemi Polytechnic, School of Technology Jokiv\[ADoubleDot]yl\[ADoubleDot] 11, 96300 Rovaniemi, Finland veikko.keranen@ramk.fi http://south.rotol.ramk.fi\ \>", "Text", TextAlignment->Center, TextJustification->0], Cell[TextData[{ StyleBox["Abstract", FontWeight->"Bold"], "\nIn 1906 Axel Thue [34] started the systematic study of structures in \ words. Consequently, he studied basic objects of theoretical computer science \ long before the invention of the computer or DNA. In 1961 Paul Erd\ \[ODoubleDot]s [13] raised the question whether abelian squares can be \ avoided in infinitely long words. In 1992, we presented in [19], see also \ [20", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "23], an abelian square-free (a-2-free) endomorphism ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " on the four letter alphabet ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], " = {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ", ", StyleBox["c", FontSlant->"Italic"], ", ", StyleBox["d", FontSlant->"Italic"], "}. The size of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], ", i.e. ", Cell[BoxData[ \(TraditionalForm\` | \)]], Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["abcd", FontSlant->"Italic"], ")", Cell[BoxData[ \(TraditionalForm\` | \)]], ", is equal to 4\[Times]85. Until now, all known methods for \ constructing arbitrarily long a-2-free words on ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], " have been based on the structure of this ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "; see Arturo Carpi [4", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "6]. \n\tIn this paper, we report of a completely new endomorphism ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], ", the iteration of which produces an infinite abelian square-free word. \ The size of ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " is 4\[Times]98, and the image words for letters are constructed, in \ part, differently from the case of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], ". For ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " they were directly obtained by permutating letters cyclically. The \ endomorphism ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " is not an a-2-free endomorphism itself, since it does not preserve the \ a-2-freeness of all words of length 7. However, ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " can be used together with ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " to produce a-2-free DT0L-languages of unlimited size. Here \ DT0L-languages mean deterministic context-independent Lindenmayer languages \ produced by using compositions of endomorphisms \[Dash] so called tables; see \ [32, p.188]. Indeed, by using Carpi's algorithm [4] for prefixes of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ") and ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], "), and a modified version of this algorithm, one can check the following \ fact: for any a-2-free words ", Cell[BoxData[ \(TraditionalForm\`w\_1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`w\_2\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`w\_1\)]], " does not contain a certain subword pattern, ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", Cell[BoxData[ \(TraditionalForm\`w\_1\)]], ") and ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", Cell[BoxData[ \(TraditionalForm\`w\_2\)]], ") are always a-2-free and avoid all undesirable patterns that would, in \ the case of ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], ", lead to an abelian-square in the next iteration step.\n\tIt is \ anticipated that later on this new result will lead to a sharper bound for \ the base number (~1.000021) found in [5], where Carpi showed that t", StyleBox["he number of a-2-free words over 4 letters of length ", FontFamily->"Times New Roman"], StyleBox["n", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" is ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], StyleBox[" ", FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ StyleBox[\(1.000021\^n\), FontSize->10], TraditionalForm]], FontFamily->"Times New Roman", FontSize->7], ".\n\tWe explain extensive computer aided searches that have been carried \ out over 11 years to find new ways of constructing a-2-free words over 4 \ letters. In this process, we have encountered some unintuitive non-linear \ phenomena which, however, are in accordance with the complex behaviour of \ simple systems studied by Stephen Wolfram in his long-awaited book [35]. For \ example, two same looking initial values for prefixes and suffixes of image \ words for letters may yield 1000-fold running times when searching through \ all possibilities for proper infixes! We also analyse the structure of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " in terms of subwords, and discuss some open problems." }], "Text"], Cell[TextData[{ "\n", StyleBox["1 ", FontWeight->"Bold"], " ", StyleBox["Introduction", FontWeight->"Bold"], "\n\nIn theoretical computer science, structures and patterns in words \ (strings) constitute a natural and central research topic. As mentioned \ above, the systematic study of word structures, i.e., combinatorics on words, \ was started by Axel Thue (1863\[Dash]1922) in [34] at the beginning of the \ 20th century. One of the remarkable discoveries made by Thue is that the \ consecutive repetitions of non-empty subwords (squares) can be avoided in \ infinite words over a three letter alphabet. As a simple example of the \ square concept, consider the finite words ", StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["c", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], StyleBox[" ", FontSize->9, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], " and ", StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["d", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->9, FontSlant->"Italic"], StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["d", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->9, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], ". The first word does not contain any square, i.e., it is square-free, \ whereas the second word contains the underlined square ", StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["d", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->9, FontSlant->"Italic"], StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["d", FontSlant->"Italic", FontVariations->{"Underline"->True}], " as a subword.\n\tThue also showed that over a binary alphabet one can \ construct arbitrarily long words which do not contain any triple repetitions \ (cubes), i.e., factors occurring three times in succession. Unfortunately, \ Thue's results were forgotten for a long time, and they have been \ rediscovered and republished again and again \[Dash] at least a dozen of \ times as noted in [9]. Indeed, repetition-free words have been used in \ various fields of mathematics. For example, in formal languages, in \ connection with unending games, and in symbolic dynamics (which constitutes a \ tool for studying chaos). Moreover, repetition-free words have served in many \ ways in the procedure of solving the famous Burnside problem from 1902. The \ question asked by Burnside was: is every group finite when it has a finite \ number of generators and satisfies the identity relation ", Cell[BoxData[ \(TraditionalForm\`x\^n\)]], " = 1 for some natural number ", StyleBox["n", FontSlant->"Italic"], "? Among other infinite repetition-free words, cube-free words over a \ binary alphabet were utilized in showing that certain Burnside groups can be \ infinite [1, pp.32\[Dash]33]. \n\tThe above mentioned square-freeness \ property of words is by no means trivial to prove. The tool which Thue \ invented for constructing square-free words, namely the concept of a \ repetition-free morphism, is still today a basic device in the study of \ avoidable patterns in words. Repetition-free morphisms are mappings between \ free monoids that preserve the repetition-freeness of words. The iteration of \ such a (non-trivial) morphism produces a repetition-free infinite word. \ Morphisms possessing this property have been sharply characterized in \ [4,8,17,18,25,26]. These results concern different types of repetitions and \ alphabet sizes. Informally speaking, most of the characterizational results \ for morphisms say that in order to test the repetition-freeness of a given \ morphism, one has only to check whether the image words of short \ repetition-free words are repetition-free. A general survey of these and \ related results (achieved before 1984) is given in [3]. For a short survey of \ Thue's results concerning repetition-free words and their applications, see \ [15]. Fundamental topics are discussed in [27,33]. \n\tIn a paper from 1961, \ see [13, p.240], Paul Erd\[ODoubleDot]s (1913\[Dash]1996) raised the question \ whether abelian squares can be avoided in infinitely long words, i.e., \ whether there exist infinitely many abelian square-free words over a given \ alphabet. Here, an abelian square means a non-empty word ", StyleBox["uv", FontSlant->"Italic"], ", where ", StyleBox["u", FontSlant->"Italic"], " and ", StyleBox["v", FontSlant->"Italic"], " are permutations of each other ", StyleBox["(Niels Henrik Abel ", FontWeight->"Plain"], "1802\[Dash]", StyleBox["1829)", FontWeight->"Plain"], ". For example, ", StyleBox["a", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["b", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["c", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->8, FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["b", FontSlant->"Italic", FontVariations->{"Underline"->True}], " is an abelian square. A word is called abelian square-free, if it does \ not contain any abelian square as a subword. For example, the word ", StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["c", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["b", FontSlant->"Italic"], StyleBox[" ", FontSize->2, FontSlant->"Italic"], StyleBox["a", FontSlant->"Italic"], " is abelian square-free, while ", StyleBox["ab", FontSlant->"Italic"], StyleBox[" ", FontSize->8, FontSlant->"Italic"], StyleBox["cabdc", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ", FontSize->9, FontSlant->"Italic"], StyleBox["bcacd", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" ac ", FontSlant->"Italic"], " is not. \n\tLater, in a 1970 paper, Pleasants [31] showed that there \ exists an infinite abelian square-free word over five letters. In 1991, see \ Ker\[ADoubleDot]nen [19] the year after, we managed to show that the same \ holds true also in the case of four letters. It is easily seen that abelian \ squares cannot be avoided over a three letter alphabet. Indeed, in this \ alphabet, each word of length 8 contains an abelian square, cf. Section 9 \ below. In [12] Entringer et al. showed that every infinite word over a binary \ alphabet contains arbitrarily long abelian squares. Due to Dekking [10] it is \ known that abelian fourth [third] power repetitions can be avoided in \ infinite words over two [three] letters.\n\tAn application of Dekking's \ result was given by Justin et al. in [16], where it was shown that a finitely \ generated semigroup is uniformly repetitive if and only if it is finite. In \ [30] Pirillo et al. used similar kind of reasoning when proving, among other \ results, that the additive semigroup ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalN]\^+\)\)]], " is not uniformly 4-repetitive. It seems to be an open problem whether \ ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalN]\^+\)\)]], " is uniformly 2-repetitive or 3-repetitive. In all these considerations \ the use of van der Waerden's theorem has been very central. In Lothaire [27, \ pp.55", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "62] van der Waerden's theorem was used to show that every morphism from a \ free semigroup ", Cell[BoxData[ \(TraditionalForm\`\(A\^+\)\)]], ", where ", StyleBox["A", FontSlant->"Italic"], " is finite, to ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalN]\^+\)\)]], " is repetitive. This means ", StyleBox["that every long enough sequence on a finite set of integers \ contains two adjacent segments (not necessarily of the same length) that have \ the same sum. \n\tThe", FontFamily->"Times New Roman"], " original problem concerning abelian squares has attracted attention also \ in the research of free partially commutative monoids, see for instance \ [7,11]. Moreover, abelian square-free words have aroused interest in \ algorithmic music, see e.g. Laakso [24]. \n\tIn [4] Carpi gave sufficient \ conditions for morphisms to preserve abelian ", StyleBox["k", FontSlant->"Italic"], "th power-freeness of words. A conjecture is that these conditions yield an \ effective characterization also for abelian square-free endomorphisms on a \ four letter alphabet ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], " = {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ", ", StyleBox["c", FontSlant->"Italic"], ", ", StyleBox["d", FontSlant->"Italic"], "}. However, new examples of relatively short abelian square-free \ endomorphisms ", StyleBox["g ", FontSlant->"Italic"], " of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], ", possibly with the size ", Cell[BoxData[ \(TraditionalForm\` | \)]], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["abcd", FontSlant->"Italic"], ")", Cell[BoxData[ \(TraditionalForm\` | \)]], " < 4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], "85 = 340 ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " provided they exist, have turned out to be extremely hard to find. Thus \ far, after 1992 (when we presented ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " in [19]), the only new abelian square-free endomorphisms and \ substitutions have been found by Carpi [5], cf. also [6, pp.80", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "81]. However, these mappings are all based on the structure of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], ". Moreover, the size of these endomorphisms and substitutions is huge, it \ is around 4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], "(", Cell[BoxData[ \(TraditionalForm\`85\^4\)]], Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " 1) ", Cell[BoxData[ \(TraditionalForm\` \[TildeEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\`209\[CenterDot]10\^6\)]], ", or so [actually, a similar favourable result regarding the size 4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], "(", Cell[BoxData[ \(TraditionalForm\`85\^3\)]], Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " 85) ", Cell[BoxData[ \(TraditionalForm\` \[TildeEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\`2.46\[CenterDot]10\^6\)]], " is also quoted to be found with the aid of computers]. These \ substitutions, and the endomorphisms derived from them, are constructed by \ deleting distinct occurrences of one letter in ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "4"], TraditionalForm]]], "(", StyleBox["x", FontSlant->"Italic"], "), ", StyleBox["x", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], ". Indeed, Carpi showed in [5] that there exists exactly one abelian \ square-free word ", StyleBox["w ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], " which can be obtained by deleting an occurrence of a letter in ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["d", FontSlant->"Italic"], "). The letter that can be deleted is the", StyleBox[" ", FontSlant->"Italic"], "6349th letter (", StyleBox["a", FontSlant->"Italic"], ") of ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["d", FontSlant->"Italic"], "). Furthermore, it turns out that both ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["c", FontSlant->"Italic"], ") ", StyleBox["w", FontSlant->"Italic"], " and ", StyleBox["w", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["c", FontSlant->"Italic"], ") are abelian square-free. By using these substitutions Carpi then showed \ that the number of abelian square-free words of each length grows \ expenentially, and, interestingly enough, that the monoid of (uniform) \ abelian square-free endomorphisms of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], " is not finitely generated.\n\tThe words ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["x", FontSlant->"Italic"], "), ", StyleBox["x", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], ", of our morphism are obtained by cyclically permutating the letters in \ ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], "). This method was already used by Pleasants [31] in connection with five \ letters. Consequently, both of these endomorphisms are uniformly growing. The \ size of Pleasants' endomorphism is 5", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], "15 = 75. In our case, we could check by using computers that the morphism \ size 4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], "85 = 340, in spite of its largeness, is known to be minimal, as far as we \ consider those abelian square-free endomorphisms which are constructed by \ using cyclic permutation of letters in ", Cell[BoxData[ \(TraditionalForm\`g\)]], "(", StyleBox["x", FontSlant->"Italic"], "), ", StyleBox["x", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], ".\n\tThe structure of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " in terms of reappearing subwords \[Dash] also as cyclic permutations, so \ called grey words, and mirror images \[Dash] turns out to be somewhat \ surprising as we will see in Section 4 below. An analogous analysis for ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " is not available as yet. The frequency of (ordinary) subwords in D0L \ words was studied in Frid [14]. For a generalization of abelian squares, see \ Avgustinovich and Frid [2]." }], "Text"], Cell[TextData[{ StyleBox["\n", FontFamily->"Times New Roman", FontWeight->"Bold"], StyleBox["2 Preliminaries", FontWeight->"Bold"], " \n\nIn this section we present most of the terminology necessary for \ understanding the mathematical structures and reasoning involved in this \ paper and", StyleBox[" ", FontFamily->"Verdana", FontSize->9, FontSlant->"Italic"], "in literature.\n\tAn ", StyleBox["alphabet", FontSlant->"Italic"], " \[CapitalSigma] is a finite non-empty set of abstract symbols called \ ", StyleBox["letters", FontSlant->"Italic"], ". A ", StyleBox["word", FontSlant->"Italic"], " (", StyleBox["string", FontSlant->"Italic"], ") over ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " is a finite (unless otherwise indicated) string, or sequence, of letters \ belonging to ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". The set of all words [non-empty words] over ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " is denoted by ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " [", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^+\)\)]], "]. On the ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], ", the associative binary operation of ", StyleBox["catenation", FontSlant->"Italic"], " is defined. For words ", StyleBox["u ", FontSlant->"Italic"], "and ", StyleBox["v", FontSlant->"Italic"], ", it is the juxtaposition ", StyleBox["uv", FontSlant->"Italic"], ". The ", StyleBox["empty word", FontSlant->"Italic"], ", which is the neutral element of catenation, is denoted by ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], ". The algebraic structures ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^+\)\)]], " are called, respectively, the free monoid and the free semigroup \ generated by ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". \n\tLet ", StyleBox["w", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`x\_1\)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CenterEllipsis]\)]], " ", Cell[BoxData[ \(TraditionalForm\`x\_m\)]], ", ", Cell[BoxData[ \(TraditionalForm\`x\_i\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". The ", StyleBox["length", FontSlant->"Italic"], " of the word ", StyleBox["w", FontSlant->"Italic"], ", denoted by |", StyleBox[" ", FontSize->7], StyleBox["w", FontSlant->"Italic"], StyleBox[" ", FontSize->7, FontSlant->"Italic"], "|, is the number of occurrences of letters in ", StyleBox["w", FontSlant->"Italic"], ", i.e., |", StyleBox[" ", FontSize->7], StyleBox["w", FontSlant->"Italic"], StyleBox[" ", FontSize->7, FontSlant->"Italic"], "| = ", StyleBox["m", FontSlant->"Italic"], ". Let ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " = { ", Cell[BoxData[ \(TraditionalForm\`a\_1\)]], ", \[Ellipsis] , ", Cell[BoxData[ \(TraditionalForm\`a\_n\)]], "}. The number of occurrences of one letter ", StyleBox["x", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " in ", StyleBox["w", FontSlant->"Italic"], " is denoted by ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(w\)\( | \_x\)\)\)]], ", or simply by ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(w\)\( | \_i\)\)\)]], " if ", StyleBox["x", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], ". The notation ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_\[CapitalSigma]\)]], "(", StyleBox["w", FontSlant->"Italic"], ") stands for the ", StyleBox["Parikh vector", FontSlant->"Italic"], " of ", StyleBox["w", FontSlant->"Italic"], ", i.e., ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_\[CapitalSigma]\)]], "(", StyleBox["w", FontSlant->"Italic"], ") = (", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(w\)\( | \_1\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Ellipsis]\)]], " , ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(w\)\( | \_n\)\)\)]], "). Usually we will omit the subscript ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " and write simply ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\)]], " instead of ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_\[CapitalSigma]\)]], ". Quite interchangeably with the Parikh vector notation also formal sums \ ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_s\)]], "(", StyleBox["w", FontSlant->"Italic"], ") = ", Cell[BoxData[ FormBox[ RowBox[{ UnderscriptBox["\[Sum]", RowBox[{"x", "\[Element]", RowBox[{"{", RowBox[{ FormBox[\(a\_1\), "TraditionalForm"], ",", "\[Ellipsis]", ",", " ", FormBox[\(a\_n\), "TraditionalForm"]}], "}"}]}]], " ", RowBox[{ FormBox[\(k\_x\), "TraditionalForm"], " ", StyleBox["x", FontSlant->"Italic"]}]}], TraditionalForm]]], ", with ", Cell[BoxData[ \(TraditionalForm\`k\_x\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\)]], ", are used. For example ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_s\)]], "(", StyleBox["abacaba", FontSlant->"Italic"], ") = 4", StyleBox["a", FontSlant->"Italic"], " + 2", StyleBox["b", FontSlant->"Italic"], " + ", StyleBox["c", FontSlant->"Italic"], ". Thus ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\_s\)]], "(", StyleBox["w", FontSlant->"Italic"], "), with ", StyleBox["w ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", is an element of the abelian free monoid ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\^\[CapitalSigma]\)]], " generated by ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". We will also consider differences of Parikh vectors and differences of \ formal sums. Consequently, these vectors and sums are extended into elements \ of the abelian free group ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\^\[CapitalSigma]\)]], " generated by ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". The neutral element of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\^\[CapitalSigma]\)]], " is denoted by ", Cell[BoxData[ FormBox[ StyleBox["0", FontWeight->"Bold"], TraditionalForm]]], ".\n\tA word ", StyleBox["u", FontSlant->"Italic"], " is called a ", StyleBox["subword", FontSlant->"Italic"], " of a word ", StyleBox["w", FontSlant->"Italic"], ", if ", StyleBox["w", FontSlant->"Italic"], " = ", StyleBox["p", FontSlant->"Italic"], StyleBox[" ", FontSize->7, FontSlant->"Italic"], StyleBox["u", FontSlant->"Italic"], StyleBox[" ", FontSize->7, FontSlant->"Italic"], StyleBox["s ", FontSlant->"Italic"], "for some words ", StyleBox["p", FontSlant->"Italic"], " and ", StyleBox["s", FontSlant->"Italic"], ". The notation SW(", StyleBox["w", FontSlant->"Italic"], ") stands for the set of all subwords of ", StyleBox["w", FontSlant->"Italic"], ". If ", StyleBox["p", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], " [", StyleBox["s", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], "], then ", StyleBox["u", FontSlant->"Italic"], " is called a ", StyleBox["prefix", FontSlant->"Italic"], " [a ", StyleBox["suffix", FontSlant->"Italic"], "] of ", StyleBox["w", FontSlant->"Italic"], ". By PREF(", StyleBox["w", FontSlant->"Italic"], ") [SUFF(", StyleBox["w", FontSlant->"Italic"], ")] we mean the set of all prefixes [suffixes] of ", StyleBox["w", FontSlant->"Italic"], ". The notation pref(", StyleBox["w", FontSlant->"Italic"], ") [suff(", StyleBox["w", FontSlant->"Italic"], ")] denotes an element in PREF(", StyleBox["w", FontSlant->"Italic"], ") [SUFF(", StyleBox["w", FontSlant->"Italic"], ")]. In the case ", StyleBox["w", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[NotEqual] \)]], " \[Lambda] we write first(", StyleBox["w", FontSlant->"Italic"], ") [last(", StyleBox["w", FontSlant->"Italic"], ")] to denote the first [the last] letter of ", StyleBox["w", FontSlant->"Italic"], ".\n\tLet ", StyleBox["k", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 2 be a given integer. A ", StyleBox["k-repetition", FontSlant->"Italic"], " [an ", StyleBox["abelian k-repetition", FontSlant->"Italic"], "] is a non-empty word of the form ", Cell[BoxData[ \(TraditionalForm\`R\^k\)]], " [", Cell[BoxData[ \(TraditionalForm\`P\_1\)]], Cell[BoxData[ \(TraditionalForm\`\[CenterEllipsis]\)]], Cell[BoxData[ \(TraditionalForm\`P\_k\)]], ", where ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(P\_\[Mu]\), "TraditionalForm"], ")"}], " ", "=", " ", RowBox[{"\[Psi]", "(", FormBox[\(P\_\[Nu]\), "TraditionalForm"], ")"}]}], TraditionalForm]]], " for all ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ \[Mu]\ < \ \[Nu]\ \[LessEqual] \ \ k\)]], ", i.e., ", Cell[BoxData[ \(TraditionalForm\`P\_i\)]], ":s are permutations of each other]. Instead of [abelian] 2- and \ 3-repetitions, terms [", StyleBox["abelian", FontSlant->"Italic"], "] ", StyleBox["squares", FontSlant->"Italic"], " and [", StyleBox["abelian", FontSlant->"Italic"], "] ", StyleBox["cubes", FontSlant->"Italic"], " are often used. A word or an ", Cell[BoxData[ \(TraditionalForm\`\[Omega]\)]], "-word (explained below) is called ", StyleBox["k-repetition free", FontSlant->"Italic"], " [", StyleBox["abelian k-repetition free", FontSlant->"Italic"], ", or ", StyleBox["k-free in the abelian sense", FontSlant->"Italic"], "], or in short ", StyleBox["k-free", FontSlant->"Italic"], " [", StyleBox["a-k-free", FontSlant->"Italic"], "], if it does not contain any ", StyleBox["k", FontSlant->"Italic"], "-repetition [abelian ", StyleBox["k", FontSlant->"Italic"], "-repetition] as a subword. A word sequence or a word set is ", StyleBox["k-free", FontSlant->"Italic"], " [", StyleBox["a-k-free", FontSlant->"Italic"], "], if all words in it are ", StyleBox["k", FontSlant->"Italic"], "-free [a-", StyleBox["k", FontSlant->"Italic"], "-free]. If, for a fixed ", StyleBox["k", FontSlant->"Italic"], ", it is possible to construct arbitrarily long (infinite) a-", StyleBox["k", FontSlant->"Italic"], "-free (or other pattern-free) words over a given alphabet ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", then we say that abelian ", StyleBox["k", FontSlant->"Italic"], "-repetitions (or those patterns) are ", StyleBox["avoidable", FontSlant->"Italic"], " over ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". \n\tSubsets of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " are called ", StyleBox["languages", FontSlant->"Italic"], " over ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". The ", StyleBox["catenation", FontSlant->"Italic"], " of languages ", StyleBox["L", FontSlant->"Italic"], " and ", Cell[BoxData[ \(TraditionalForm\`L\_1\)]], ", denoted by ", StyleBox["L", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`L\_1\)]], ", is the language {", StyleBox["uv", FontSlant->"Italic"], " | ", StyleBox["u", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", StyleBox["L", FontSlant->"Italic"], ", ", StyleBox["v", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`L\_1\)]], "}. The notation ", Cell[BoxData[ \(TraditionalForm\`L\^i\)]], ", where ", StyleBox["L", FontSlant->"Italic"], " is a language and ", Cell[BoxData[ \(TraditionalForm\`i\ \[Element] \ \[DoubleStruckCapitalN]\)]], ", is defined as follows: ", Cell[BoxData[ \(TraditionalForm\`L\^0\)]], " = {", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], "} and ", Cell[BoxData[ \(TraditionalForm\`L\^\(i + 1\)\)]], " = ", Cell[BoxData[ \(TraditionalForm\`L\^i\)]], StyleBox["L", FontSlant->"Italic"], ". Let ", Cell[BoxData[ \(TraditionalForm\`\(L\^*\)\)]], " = ", Cell[BoxData[ \(TraditionalForm\`\[Union]\_\(i = 0\)\%\[Infinity]\)]], " ", Cell[BoxData[ \(TraditionalForm\`L\^i\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(L\^+\)\)]], " = ", Cell[BoxData[ \(TraditionalForm\`\[Union]\_\(i = 1\)\%\[Infinity]\)]], " ", Cell[BoxData[ \(TraditionalForm\`L\^i\)]], ". If a language contains only one word, say ", StyleBox["w", FontSlant->"Italic"], ", then we sometimes write ", StyleBox["w", FontSlant->"Italic"], " instead of {", StyleBox["w", FontSlant->"Italic"], "}; especially, ", Cell[BoxData[ \(TraditionalForm\`\(w\^*\)\)]], " = {", Cell[BoxData[ \(TraditionalForm\`w\^i\)]], "| ", StyleBox["i", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 0} and ", Cell[BoxData[ \(TraditionalForm\`\(w\^+\)\)]], " = {", Cell[BoxData[ \(TraditionalForm\`w\^i\)]], "| ", StyleBox["i", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 1}.\n\tFor a language ", StyleBox["L", FontSlant->"Italic"], " we write ", StyleBox["Q", FontSlant->"Italic"], "(", StyleBox["L", FontSlant->"Italic"], "), where ", StyleBox["Q", FontSlant->"Italic"], " is SW, PREF or SUFF, to denote the set ", Cell[BoxData[ FormBox[ SubscriptBox["\[Union]", RowBox[{ StyleBox["w", FontSlant->"Italic"], " ", "\[Element]", StyleBox["L", FontSlant->"Italic"]}]], TraditionalForm]]], " ", StyleBox["Q", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], "). Moreover, for ", Cell[BoxData[ \(TraditionalForm\`n\ \[Element] \ \[DoubleStruckCapitalN]\)]], ", we write ", Cell[BoxData[ \(TraditionalForm\`Q\_n\)]], "(", StyleBox["L", FontSlant->"Italic"], ") to denote the words in ", StyleBox["Q", FontSlant->"Italic"], "(", StyleBox["L", FontSlant->"Italic"], ") of length = ", StyleBox["n", FontSlant->"Italic"], ". The notation ", Cell[BoxData[ \(TraditionalForm\`pref\_n\)]], "(", StyleBox["w", FontSlant->"Italic"], ") [", Cell[BoxData[ \(TraditionalForm\`suff\_n\)]], "(", StyleBox["w", FontSlant->"Italic"], ")] is used for an element in ", Cell[BoxData[ \(TraditionalForm\`PREF\_n\)]], "(", StyleBox["w", FontSlant->"Italic"], ") [", Cell[BoxData[ \(TraditionalForm\`SUFF\_n\)]], "(", StyleBox["w", FontSlant->"Italic"], ")].\n\tA ", StyleBox["morphism", FontSlant->"Italic"], " ", StyleBox["h", FontSlant->"Italic"], " is a mapping between free monoids ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], " with ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["uv", FontSlant->"Italic"], ") = ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["u", FontSlant->"Italic"], ")", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["v", FontSlant->"Italic"], ") for every ", StyleBox["u", FontSlant->"Italic"], " and ", StyleBox["v", FontSlant->"Italic"], " in ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], ". Especially, ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], ") = ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], ". A morphism ", StyleBox["h", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], ", being compatible with the catenation of words, is uniquely defined, if \ the word ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["x", FontSlant->"Italic"], ") ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], " is (effectively) given for each ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \[CapitalSigma]\)]], ". If ", Cell[BoxData[ \(TraditionalForm\`\[CapitalDelta]\ = \ \[CapitalSigma]\)]], ", we call ", StyleBox["h ", FontSlant->"Italic"], " an ", StyleBox["endomorphism", FontSlant->"Italic"], " (and usually write ", StyleBox["g ", FontSlant->"Italic"], " instead of ", StyleBox["h", FontSlant->"Italic"], "). For a morphism ", StyleBox["h", FontSlant->"Italic"], " and a language ", StyleBox["L", FontSlant->"Italic"], " we define ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["L", FontSlant->"Italic"], ") = {", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") | ", Cell[BoxData[ \(TraditionalForm\`w\ \[Element] \ L\)]], "}. A morphism ", StyleBox["h", FontSlant->"Italic"], " is termed ", StyleBox["uniformly growing", FontSlant->"Italic"], ", if |", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["x", FontSlant->"Italic"], ")| = |", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["y", FontSlant->"Italic"], ")| ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 2 for every ", StyleBox["x", FontSlant->"Italic"], " and ", Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ \[CapitalSigma]\)]], ".\n\tFor a given integer ", StyleBox["k", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 2, a morphism ", StyleBox["h", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], " is called ", StyleBox["k-free", FontSlant->"Italic"], " [", StyleBox["a-k-free", FontSlant->"Italic"], "], if ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") is ", StyleBox["k", FontSlant->"Italic"], "-free [a-", StyleBox["k", FontSlant->"Italic"], "-free] for every ", StyleBox["k", FontSlant->"Italic"], "-free [a-", StyleBox["k", FontSlant->"Italic"], "-free] word ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\^*\), "TraditionalForm"]}], TraditionalForm]]], ".\t\n\tAs regards the ", StyleBox["L-systems", FontSlant->"Italic"], " (Aristid Lindenmayer 1925", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "1989), we specify the following concepts. A ", StyleBox["D0L-system", FontSlant->"Italic"], " is a triple ", StyleBox["G", FontSlant->"Italic"], " = (", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", ", StyleBox["g", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), where ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " is an alphabet, ", StyleBox["g", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " is an endomorphism, and ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ", called the ", StyleBox["axiom", FontSlant->"Italic"], ", is a word over ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". The (", StyleBox["word", FontSlant->"Italic"], ") ", StyleBox["sequence", FontSlant->"Italic"], " ", StyleBox["S", FontSlant->"Italic"], "(", StyleBox["G", FontSlant->"Italic"], ") generated by ", StyleBox["G", FontSlant->"Italic"], " consists of the words\n\t\n\t\t", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], " = ", Cell[BoxData[ \(TraditionalForm\`g\^0\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), ", Cell[BoxData[ \(TraditionalForm\`g\^1\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), ", Cell[BoxData[ \(TraditionalForm\`g\^2\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), ", Cell[BoxData[ \(TraditionalForm\`g\^3\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), ... , \n\nwhere ", Cell[BoxData[ \(TraditionalForm\`g\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ") = ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^\(i - 1\)\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")) for ", Cell[BoxData[ \(TraditionalForm\`i\ \[GreaterEqual] \ 1\)]], ". The ", StyleBox["language", FontSlant->"Italic"], " of ", StyleBox["G", FontSlant->"Italic"], " is defined by ", StyleBox["L", FontSlant->"Italic"], "(", StyleBox["G", FontSlant->"Italic"], ") = {", Cell[BoxData[ \(TraditionalForm\`g\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ") | ", Cell[BoxData[ \(TraditionalForm\`i\ \[GreaterEqual] \ 0\)]], "}. Languages [sequences] defined by a D0L-system are referred to as ", StyleBox["D0L-languages", FontSlant->"Italic"], " [", StyleBox["D0L-sequences", FontSlant->"Italic"], "]. D0L-systems provide a very convenient way for defining languages and \ infinite words. Furthermore, if ", StyleBox["g", FontSlant->"Italic"], " and ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], " are ", StyleBox["k", FontSlant->"Italic"], "-free [a-", StyleBox["k", FontSlant->"Italic"], "-free], then the iteration of ", StyleBox["g", FontSlant->"Italic"], " will yield a ", StyleBox["k", FontSlant->"Italic"], "-free [a-", StyleBox["k", FontSlant->"Italic"], "-free] D0L-sequence. An ", StyleBox["HD0L-system", FontSlant->"Italic"], " is a 5-tuple ", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], " = (", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[CapitalDelta]\)]], ", ", StyleBox["g", FontSlant->"Italic"], ", ", StyleBox["h", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), where (", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", ", StyleBox["g", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ") is a D0L-system, called the underlying D0L-system of ", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], ", \[CapitalDelta] is an alphabet, and ", StyleBox["h", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], " is a morphism. The ", StyleBox["HD0L-sequence", FontSlant->"Italic"], " ", StyleBox["S", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], ") generated by ", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], " consists of the words\n\n\t\t", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ") = ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^0\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")), ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^1\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")), ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^2\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")), ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^3\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")), ... , \n\nand the ", StyleBox["HD0L-language ", FontSlant->"Italic"], "of ", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], " is the set ", StyleBox["L", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`G\_1\)]], ") = {", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`g\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ")) | ", Cell[BoxData[ \(TraditionalForm\`i\ \[GreaterEqual] \ 0\)]], "}. A DT0L", StyleBox["-system", FontSlant->"Italic"], " is a triple ", Cell[BoxData[ \(TraditionalForm\`G\_2\)]], " = (", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", ", StyleBox["H", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], "), where ", StyleBox["H", FontSlant->"Italic"], " is a finite non-empty set of morphisms (called tables) and (", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ", ", StyleBox["h", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], ") is a D0L-system for every ", Cell[BoxData[ \(TraditionalForm\`h\ \[Element] \ H\)]], ". The ", StyleBox["DT0L-language ", FontSlant->"Italic"], "of ", Cell[BoxData[ \(TraditionalForm\`G\_2\)]], " is the set ", StyleBox["L", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`G\_2\)]], ") = {", StyleBox["w ", FontSlant->"Italic"], "| ", StyleBox["w", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\_0\)]], " or ", StyleBox["w", FontSlant->"Italic"], " = ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(h\_k\), "TraditionalForm"], "\[CenterEllipsis]", RowBox[{ FormBox[\(h\_1\), "TraditionalForm"], "(", FormBox[\(\[Alpha]\_0\), "TraditionalForm"], ")"}]}], TraditionalForm]]], ", where the compositions ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(h\_k\), "TraditionalForm"], "\[CenterEllipsis]", FormBox[\(h\_1\), "TraditionalForm"]}], TraditionalForm]]], " of morphims are constructed from ", Cell[BoxData[ \(TraditionalForm\`h\_1\)]], ", ..., ", Cell[BoxData[ \(TraditionalForm\`h\_k\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", StyleBox["H", FontSlant->"Italic"], "}. Obviously, a DT0L-system can be regarded as a D0L-system, when ", StyleBox["H", FontSlant->"Italic"], " contains only one (endo)morphism. For a thorough discussion of various \ L-systems we refer the reader to Rozenberg and Salomaa [32].\n\tAn ", Cell[BoxData[ \(TraditionalForm\`\[Omega]\)]], "-", StyleBox["word", FontSlant->"Italic"], " is an infinite sequence, from left to right, of letters of an alphabet \ ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". Thus an ", Cell[BoxData[ \(TraditionalForm\`\[Omega]\)]], "-word can be identified with a mapping of ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalN]\_+\)\)]], " into ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ". One can construct an ", Cell[BoxData[ \(TraditionalForm\`\[Omega]\)]], "-word, for example, by iterating an endomorphism ", StyleBox["g", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\ \[NotElement] \ g(\[CapitalSigma])\)]], " and ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["x", FontSlant->"Italic"], ") = ", StyleBox["xw ", FontSlant->"Italic"], " for some ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \[CapitalSigma]\)]], ", ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\^+\), "TraditionalForm"]}], TraditionalForm]]], ". Such a morphism ", StyleBox["g", FontSlant->"Italic"], " is called ", StyleBox["prefix preserving", FontSlant->"Italic"], " for the reason that ", Cell[BoxData[ \(TraditionalForm\`g\^i\)]], "(", StyleBox["x", FontSlant->"Italic"], ") is a proper prefix of ", Cell[BoxData[ \(TraditionalForm\`g\^\(i + 1\)\)]], "(", StyleBox["x", FontSlant->"Italic"], ") whenever ", StyleBox["i", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 0. An ", Cell[BoxData[ \(TraditionalForm\`\[Omega]\)]], "-word is obtained as the \"limit\" of the sequence ", Cell[BoxData[ \(TraditionalForm\`g\^i\)]], "(", StyleBox["a", FontSlant->"Italic"], "); ", StyleBox["i", FontSlant->"Italic"], " = 0, 1, 2, \[Ellipsis] . " }], "Text", TextAlignment->Left, TextJustification->1], Cell[TextData[StyleBox["\n3 Some examples of repetition-free endomorphisms", FontWeight->"Bold"]], "Text"], Cell[TextData[{ "Below we use ", StyleBox["Mathematica", FontSlant->"Italic"], " to produce some examples of the iteration of an endomorphism. The first \ two examples are due to Axel Thue (1906, 1912), and the last one is our \ abelian square-free morphism ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "." }], "Text"], Cell[TextData[{ "\tThue iterated the following prefix preserving endomorphism ", StyleBox["g", FontSlant->"Italic"], ": {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " when showing the existence of a cube-free (3-free) infinite word over \ the binary alphabet {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], "}. We have used extra spaces to make the output more readable:" }], "Text"], Cell[BoxData[{ \(\(productions = {"\" \[Rule] "\", "\" \[Rule] "\"};\ \)\), "\[IndentingNewLine]", \(g[x_] := StringReplace[x, productions]\)}], "Input"], Cell[BoxData[ \(NestList[g, "\", 5]\ // TableForm\)], "Input"], Cell[BoxData[ InterpretationBox[GridBox[{ {"\<\"a\"\>"}, {"\<\"ab \"\>"}, {"\<\"ab ba \"\>"}, {"\<\"ab ba ba ab \"\>"}, {"\<\"ab ba ba ab ba ab ab ba \"\>"}, {"\<\"ab ba ba ab ba ab ab ba ba ab ab ba ab ba ba ab \ \"\>"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], TableForm[ {"a", "ab ", "ab ba ", "ab ba ba ab ", "ab ba ba ab ba ab ab ba ", "ab ba ba ab ba ab ab ba ba ab ab ba ab ba ba ab \ "}]]], "Output", FontSize->10], Cell[TextData[{ "\tThe iteration of the next endomorphim ", StyleBox["g", FontSlant->"Italic"], ": {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ",", StyleBox[" c", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ",", StyleBox[" c", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " produces longer and longer square-free (2-free) strings over the three \ letter alphabet {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ", ", StyleBox["c", FontSlant->"Italic"], "}:" }], "Text"], Cell[BoxData[ \(\(productions = {"\" \[Rule] "\", "\" \[Rule] "\", \ "\" \[Rule] \ "\", \ "\< \>" -> "\<\>"};\)\)], "Input"], Cell[BoxData[ \(NestList[g, "\", 5]\ // TableForm\)], "Input"], Cell[BoxData[ InterpretationBox[GridBox[{ {"\<\"a\"\>"}, {"\<\"abc \"\>"}, {"\<\"abc ac b \"\>"}, {"\<\"abc ac b abc b ac \"\>"}, {"\<\"abc ac b abc b ac abc ac b ac abc b \"\>"}, {"\<\"abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b \ abc ac b ac \"\>"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], TableForm[ {"a", "abc ", "abc ac b ", "abc ac b abc b ac ", "abc ac b abc b ac abc ac b ac abc b ", "abc ac b abc b ac abc ac b ac abc b abc ac b abc b ac abc b abc ac b \ ac "}]]], "Output", FontSize->9], Cell[TextData[{ "Note that this ", StyleBox["g", FontSlant->"Italic"], " is not square-free itself, since", " ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["aba", FontSlant->"Italic"], ") = ", StyleBox["a b ", FontSlant->"Italic"], StyleBox["c a c a", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox[" b c", FontSlant->"Italic"], " is not square-free !" }], "Text"], Cell[TextData[{ "\tThe abelian square-free endomorphism ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], ": {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ",", StyleBox[" c", FontSlant->"Italic"], ",", StyleBox[" d", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " {", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["b", FontSlant->"Italic"], ",", StyleBox[" c", FontSlant->"Italic"], ",", StyleBox[" d", FontSlant->"Italic"], "}", Cell[BoxData[ \(TraditionalForm\`\(\^*\)\)]], " which we found in [19] is as follows:" }], "Text"], Cell[BoxData[ StyleBox[\(g85a = \ "\";\), FormatType->StandardForm, FontFamily->"Courier New", FontSize->10]], "Input", FontSize->4], Cell[BoxData[ \(\(cyclicPermutation = {"\" \[Rule] \ "\", "\" \[Rule] \ \ "\", "\" \[Rule] \ "\", "\" \[Rule] \ "\"};\)\)], "Input"], Cell[BoxData[{ \(\(g85b = StringReplace[g85a, cyclicPermutation];\)\), "\[IndentingNewLine]", \(\(g85c = StringReplace[g85b, cyclicPermutation];\)\), "\[IndentingNewLine]", \(\(g85d = StringReplace[g85c, cyclicPermutation];\)\)}], "Input"], Cell["\<\ We define:\ \>", "Text"], Cell[BoxData[ \(myParikh[x_String] := Apply[Plus, Characters[x]]\)], "Input"], Cell[TextData[{ "and compute the length and the number of occurrences of each letter of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], ") as follows:" }], "Text"], Cell[BoxData[ \({StringLength[g85a], myParikh[g85a]}\)], "Input"], Cell[BoxData[ \({85, 19\ "a" + 21\ "b" + 27\ "c" + 18\ "d"}\)], "Output"], Cell[TextData[{ StyleBox["4 Structures in ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`g\_85\)], FontWeight->"Bold"] }], "Text"], Cell[TextData[{ "In this section, we give a pictorial representation of the structure of \ ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " in terms of reappearing subwords ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " also as cyclic permutations, grey words (in which all letters occur \ equally often), and mirror images. In the first part, cyclic permutations of \ subwords of length 26 turn out to be quite surprising. In a sense, one can \ explain these phenomena by thinking that reappearing subwords reduce the \ number of different Parikh vectors of longer successive subwords, and thus \ make avoiding of all abelian repetitions more plausible. Needless to say that \ we are still far from understanding these structures precisely.\n\tThe \ underlined letter ", StyleBox["c ", FontSlant->"Italic"], "in ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], ") means the following. As explained in the Introduction, Carpi [5] used \ substitutions derived from ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " when showing that the number of abelian square-free words of each length \ grows expenentially. Basically, he showed that there exists exactly one \ abelian square-free word ", StyleBox["w ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{"\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], " which can be obtained by deleting an occurrence of a letter in ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["b", FontSlant->"Italic"], "). The letter, that can be deleted, is the", StyleBox[" ", FontSlant->"Italic"], "6349th letter (", StyleBox["c", FontSlant->"Italic"], ") of ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["b", FontSlant->"Italic"], "). In this case, both ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["a", FontSlant->"Italic"], ") ", StyleBox["w", FontSlant->"Italic"], " and ", StyleBox["w", FontSlant->"Italic"], " ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["a", FontSlant->"Italic"], ") are also abelian square-free. This 6349th letter of ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(g\_85\), "TraditionalForm"], "2"], TraditionalForm]]], "(", StyleBox["b", FontSlant->"Italic"], ") lies inside an occurrence of the block ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], ") and is at the 59th position of that occurrence (note that 6349 = 74", Cell[BoxData[ \(TraditionalForm\`\[CenterDot]\)]], "85 + 59). The 59th letter of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], ") is the underlined ", StyleBox["c", FontSlant->"Italic"], " below." }], "Text"], Cell["\<\ Coloured subwords of length 26 are cyclic permutations of each \ other:\ \>", "Subtitle", CellMargins->{{42, Inherited}, {Inherited, Inherited}}, FontSize->10], Cell[TextData[{ "g85(a) = abcacdcbcdcadcdbdaba \n", StyleBox["cabadbabcbdbcbacbcdcacbabd", FontColor->RGBColor[0, 1, 0]], " abacadcbcdca", StyleBox["c", FontVariations->{"Underline"->True}], "\n", StyleBox["dbcbacbcdcacdcbdcdadbdcbca", FontColor->RGBColor[1, 0, 0]], ";\n\ng85(b) = bcdbdadcdadbadacabcb \n", StyleBox["dbcbacbcdcacdcbdcdadbdcbca", FontColor->RGBColor[1, 0, 0]], " bcbdbadcdadbd\n", StyleBox["acdcbdcdadbdadcadabacadcdb", FontColor->RGBColor[0, 0, 1]], ";\n\ng85(c) = cdacabadabacbabdbcdc \n", StyleBox["acdcbdcdadbdadcadabacadcdb ", FontColor->RGBColor[0, 0, 1]], "cdcacbadabaca\n", StyleBox["bdadcadabacabadbabcbdbadac", FontColor->RGBColor[1, 0, 1]], ";\n\ng85(d) = dabdbcbabcbdcbcacdad \n", StyleBox["bdadcadabacabadbabcbdbadac", FontColor->RGBColor[1, 0, 1]], " dadbdcbabcbdb \n", StyleBox["cabadbabcbdbcbacbcdcacbabd", FontColor->RGBColor[0, 1, 0]], ";" }], "Input", CellMargins->{{Inherited, -63.3125}, {Inherited, Inherited}}, AspectRatioFixed->True, FontSize->12, Background->GrayLevel[1], CellTags->"Start"], Cell["In the grey subwords below, all letters occur equally often:", \ "Subtitle", CellMargins->{{42, Inherited}, {Inherited, Inherited}}, FontSize->10], Cell[TextData[{ "g85(a) = abc ", StyleBox["acdcbcdcadcdbdabacabadbabcbd", FontColor->GrayLevel[0.500008]], StyleBox[" \n", FontColor->RGBColor[0, 1, 0]], "bcbacbc", StyleBox[" ", FontColor->RGBColor[0, 1, 0]], StyleBox["dcacbabd", FontColor->GrayLevel[0.500008]], " abac ", StyleBox["adcb ", FontColor->GrayLevel[0.500008]], "cdc ", StyleBox["acdb ", FontColor->GrayLevel[0.500008]], "cbacbcdcacdcbdcd", StyleBox[" ", FontColor->RGBColor[1, 0, 0]], StyleBox["adbdcbca", FontColor->GrayLevel[0.500008]], ";" }], "Input", AspectRatioFixed->True, FontSize->12, Background->GrayLevel[1], CellTags->"Start"], Cell[TextData[{ "g85(a) = abc ", StyleBox["acdcbcdcadcdbdabacabadbabcbd", FontColor->GrayLevel[0.500008]], StyleBox[" \n", FontColor->RGBColor[0, 1, 0]], "bcbacbcdcacba", StyleBox[" bdabacadcbcd", FontColor->GrayLevel[0.500008]], " c ", StyleBox["acdb ", FontColor->GrayLevel[0.500008]], "cbacbcdcacdcbdcd", StyleBox[" ", FontColor->RGBColor[1, 0, 0]], StyleBox["adbdcbca", FontColor->GrayLevel[0.500008]], ";" }], "Input", AspectRatioFixed->True, FontSize->12, Background->GrayLevel[1], CellTags->"Start"], Cell[TextData[{ " Some reappearing subwords ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " also as mirror images:" }], "Subtitle", CellMargins->{{42, Inherited}, {Inherited, Inherited}}, FontSize->10], Cell[BoxData[{\(g85 \((a)\) = \ abcacdcbcdcadcdbdaba\), "\n", RowBox[{ StyleBox["cabadbabcb", FontColor->RGBColor[0, 1, 0]], StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{"d", StyleBox["bcbacbcdcac", FontColor->RGBColor[0, 1, 0]]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 1, 0]], "1"], FontColor->RGBColor[0, 1, 0]], StyleBox["babd", FontColor->RGBColor[0, 1, 0]], "abaca", StyleBox["d", FontVariations->{"Underline"->False}], "cbcdcac"}], "\n", RowBox[{ RowBox[{ StyleBox[ RowBox[{ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[\(d bcba cbcdcac\), FontColor->RGBColor[1, 0, 0]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[1, 0, 0]], "1"], "dcbdcdadbdcbca"}], FontColor->RGBColor[1, 0, 0]], ";"}], "\[IndentingNewLine]"}], "\n", \(g85 \((a)\) = \ abcacdcbcdcadcd\), "\n", RowBox[{ StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{ StyleBox["bdaba", FontColor->GrayLevel[0], FontVariations->{"Underline"->False}], StyleBox["ca", FontColor->RGBColor[0, 1, 0], FontVariations->{"Underline"->False}]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontVariations->{"Underline"->True}], StyleBox["2", FontVariations->{"Underline"->False}]], FontVariations->{"Underline"->True}], StyleBox["badbabcbdbcbacbcdcacba", FontColor->RGBColor[0, 1, 0]], StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{ StyleBox["bd", FontColor->RGBColor[0, 1, 0], FontVariations->{"Underline"->False}], StyleBox["abaca", FontColor->GrayLevel[0], FontVariations->{"Underline"->False}]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontVariations->{"Underline"->True}], StyleBox["2", FontVariations->{"Underline"->False}]], FontVariations->{"Underline"->True}]}], "\n", RowBox[{ RowBox[{ RowBox[{"abacad", StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{ StyleBox["cbcdcac", FontVariations->{"Underline"->False}], StyleBox["d", FontColor->RGBColor[1, 0, 0], FontVariations->{"Underline"->False}]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontVariations->{"Underline"->True}], StyleBox["3", FontVariations->{"Underline"->False}]], FontVariations->{"Underline"->True}], StyleBox["bcba", FontColor->RGBColor[1, 0, 0]], StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox["cbcdcacd", FontColor->RGBColor[1, 0, 0], FontVariations->{"Underline"->False}], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[1, 0, 0], FontVariations->{"Underline"->True}], StyleBox["3", FontVariations->{"Underline"->False}]], FontColor->RGBColor[1, 0, 0], FontVariations->{"Underline"->True}], StyleBox["cbdcdadbdcbca", FontColor->RGBColor[1, 0, 0]]}], ";"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(g85 \((a)\)\), "=", RowBox[{ OverscriptBox[ OverscriptBox[ FrameBox["abcacdcbc", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], "\[DoubleLongRightArrow]"], "4"], "dcadcdbdaba"}]}], " "}], "\n", RowBox[{ StyleBox["cabadbabcbdbcba", FontColor->RGBColor[0, 1, 0]], StyleBox[ OverscriptBox[ StyleBox[ OverscriptBox[ StyleBox[ FrameBox["cbcdcacba", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 1, 0]], StyleBox["\[DoubleLongLeftArrow]", FontWeight->"Plain"]], FontColor->RGBColor[0, 1, 0]], "4"], FontColor->RGBColor[0, 1, 0]], StyleBox["bd", FontColor->RGBColor[0, 1, 0]], "abacadcbcdcac"}], "\n", RowBox[{ RowBox[{ StyleBox["dbcbacbcdcacdcbdcdadbdcbca", FontColor->RGBColor[1, 0, 0]], ";"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(g85 \((a)\)\), "=", RowBox[{ OverscriptBox[ OverscriptBox[ FrameBox["abcacdcb", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], "\[DoubleLongRightArrow]"], "5"], "cd", OverscriptBox[ FrameBox["cadcdbdab", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], "6"], "a"}]}], " "}], "\n", RowBox[{ StyleBox["cabadbabcbdbcbacbcdcacbab", FontColor->RGBColor[0, 1, 0]], StyleBox[ OverscriptBox[ StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{ StyleBox["d", FontColor->RGBColor[0, 1, 0]], StyleBox["abacadc", FontColor->GrayLevel[0]]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 1, 0]], "\[DoubleLongRightArrow]"], FontColor->RGBColor[0, 1, 0]], "7"], FontColor->RGBColor[0, 1, 0]], "bcdcac"}], "\n", RowBox[{ RowBox[{ StyleBox["dbcbacbcdcacdcbdcdadbdcbca", FontColor->RGBColor[1, 0, 0]], ";"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{\(g85 \((c)\)\), "=", RowBox[{ OverscriptBox[ OverscriptBox[ FrameBox["cdacabad", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], "\[DoubleLongLeftArrow]"], "7"], "abacbabdbcdc"}]}], " "}], "\n", RowBox[{ StyleBox["acdcbdcdadbdadca", FontColor->RGBColor[0, 0, 1]], StyleBox[ OverscriptBox[ StyleBox[ OverscriptBox[ StyleBox[ FrameBox["dabacadc", BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 0, 1]], "\[DoubleLongRightArrow]"], FontColor->RGBColor[0, 0, 1]], "7"], FontColor->RGBColor[0, 0, 1]], StyleBox["d", FontColor->RGBColor[0, 0, 1]], StyleBox[ OverscriptBox[ StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ StyleBox[ RowBox[{ StyleBox["b", FontColor->RGBColor[0, 0, 1]], StyleBox["cdcacba", FontColor->GrayLevel[0]]}]], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 0, 1]], "\[DoubleLongLeftArrow]"], FontColor->RGBColor[0, 0, 1]], "5"], FontColor->RGBColor[0, 0, 1]], "dabaca"}], "\n", RowBox[{ RowBox[{ StyleBox["bdadcadabacabadbabcbdbadac", FontColor->RGBColor[1, 0, 1]], ";"}], "\[IndentingNewLine]"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{\(g85 \((b)\) | g85 \((d)\)\), "=", " ", RowBox[{ RowBox[{"...", StyleBox["aba", FontColor->RGBColor[0, 0, 1]], StyleBox[ OverscriptBox[ StyleBox[ FrameBox[ RowBox[{ StyleBox["cadcdb", FontColor->RGBColor[0, 0, 1]], StyleBox["|", FontColor->GrayLevel[0]], StyleBox["dab", FontColor->GrayLevel[0]]}], BoxMargins->{{0.2, 0.2}, {0.4, 0.4}}], FontColor->RGBColor[0, 0, 1]], "6"], FontColor->RGBColor[0, 0, 1]], "dbc"}], "..."}]}], ";"}], "\[IndentingNewLine]", " ", "\[IndentingNewLine]", " "}], "\[IndentingNewLine]", RowBox[{" "}]}], "Input", CellMargins->{{Inherited, -145.938}, {Inherited, Inherited}}, AspectRatioFixed->True, FontSize->12, Background->GrayLevel[1], CellTags->"Start"], Cell[TextData[StyleBox["5 Carpi's characterisation of a-2-free morphisms", FontWeight->"Bold"]], "Text"], Cell[TextData[{ StyleBox["Proposition 1 ", FontWeight->"Bold"], "(Carpi [4]).", StyleBox[" ", FontWeight->"Bold"], "Given an integer ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 2\)]], ", two alphabets ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[CapitalDelta]\)]], ", and a morphism ", StyleBox["h", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalDelta]\^*\)\)]], ", let us denote by ", Cell[BoxData[ \(TraditionalForm\`G\_h\)]], " the subgroup of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\^\[CapitalDelta]\)]], " generated by ", Cell[BoxData[ \(TraditionalForm\`\[Psi](h(\[CapitalSigma]))\)]], ". Then, the morphism ", StyleBox["h", FontSlant->"Italic"], " is an abelian ", StyleBox["n", FontSlant->"Italic"], "th power-free (a-n-free) provided that the following conditions are \ satisfied:\n(i)\t", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") is a-n-free for every a-n-free word ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\^*\), "TraditionalForm"]}], TraditionalForm]]], " of length 2, \n(ii)\t", StyleBox["h", FontSlant->"Italic"], " is commutatively bijective (i.e. the set ", Cell[BoxData[ \(TraditionalForm\`\[Psi](h(\[CapitalSigma]))\)]], " is linearly independent),\n(iii)\tfor all ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(a\_i\), "TraditionalForm"], " ", "\[Element]", " ", "\[CapitalSigma]"}], TraditionalForm]]], ", ", Cell[BoxData[ \(TraditionalForm\`p\_i\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " PREF( ", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], ") ) ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " {", StyleBox["h", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`a\_i\)]], ")} (", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ i\ \[LessEqual] \ n\)]], ") such that\n\n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_\(j + 1\)\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_j\), "TraditionalForm"], ")"}]}], " ", "+", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_\(j - 1\)\), "TraditionalForm"], ")"}]}], " ", "\[Element]", " ", FormBox[\(G\_h\), "TraditionalForm"]}], TraditionalForm]]], ",\t\t", StyleBox["j", FontSlant->"Italic"], " = 1, 2 , ... , ", StyleBox["n", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "1,\n\nthere exists integers ", Cell[BoxData[ \(TraditionalForm\`\[Delta]\_i\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " {0,1} such that\n\n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_\(j + 1\)\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_j\), "TraditionalForm"], ")"}]}], " ", "+", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_\(j - 1\)\), "TraditionalForm"], ")"}]}], TraditionalForm]]], " = \n\t\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ FormBox[\(\[Delta]\_\(j + 1\)\), "TraditionalForm"], RowBox[{"\[Psi]", "(", RowBox[{"h", "(", FormBox[\(a\_\(j + 1\)\), "TraditionalForm"], ")"}], ")"}], " ", "\[Dash]", " ", "2", " ", FormBox[\(\[Delta]\_j\), "TraditionalForm"], RowBox[{"\[Psi]", "(", RowBox[{"h", "(", FormBox[\(a\_j\), "TraditionalForm"], ")"}], " ", ")"}]}], " ", "+", " ", RowBox[{ FormBox[\(\[Delta]\_\(j - 1\)\), "TraditionalForm"], RowBox[{"\[Psi]", "(", RowBox[{"h", "(", FormBox[\(a\_\(j - 1\)\), "TraditionalForm"], ")"}], ")"}]}]}], TraditionalForm]]], ", ", StyleBox["j", FontSlant->"Italic"], " = 1, 2 , ... , ", StyleBox["n", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "1.\n\t\t\nIf Card(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\)]], ") ", Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], " 6, then an a-", StyleBox["n", FontSlant->"Italic"], "-free morphism ", StyleBox["h ", FontSlant->"Italic"], "always satisfies conditions (i)", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "(iii). ", Cell[BoxData[ \(TraditionalForm\`\[Square]\)]], "\n\n\tInformally speaking, the condition (iii) above says that, if ", StyleBox["h", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") contains an abelian repetition (as a subword), then there is an abelian \ repetition in the underlying word ", StyleBox["w", FontSlant->"Italic"], ", too. In our case, we are interested in applying this characterisation \ when ", StyleBox["n", FontSlant->"Italic"], " = 2 (and ", StyleBox["j", FontSlant->"Italic"], " = 1). Independently of us, Carpi verified in [4] that, indeed, ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " satifies conditions (i)", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "(iii) of Proposition 1, for n = 2, and is therefore a-2-free.\n\tVille \ Mattila implemented Carpi's algorithm in [28]. Here, we use the word ", StyleBox["algorithm", FontSlant->"Italic"], ", as we wish to emphasise the process aspect of this characterisation. \ Mattila explains programming viewpoints related to this algorithm also in \ another paper, entitled ", StyleBox["Constructing Abelian Square-Free Words and Testing Morphisms with \ Mathematica", FontSlant->"Italic"], ", in this ", StyleBox["IAS", FontSlant->"Italic"], " 2002 proceedings. In that paper, and in [28], he also explains how to use \ computer algebra tools for producing a-2-free strings \[Dash] there the \ method is to solve character variables in strings by using polynomial \ inequalities.", StyleBox["\n", FontSlant->"Italic"] }], "Text"], Cell[TextData[{ StyleBox["6 A new infinite a-2-free D0L", FontWeight->"Bold", Background->GrayLevel[1]], Cell[BoxData[ \(TraditionalForm\`-\)]], StyleBox["sequence over 4 letters", FontWeight->"Bold", Background->GrayLevel[1]] }], "Text", CellDingbat->None, FontFamily->"Times New Roman"], Cell[TextData[{ "Define the endomorphism ", StyleBox["g", FontSlant->"Italic"], ": ", Cell[BoxData[ \(TraditionalForm\`\({a, b, c, d}\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\({a, b, c, d}\^*\)\)]], " as follows:\n\n\t", StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["a", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FontFamily->"Times New Roman"], " = ", StyleBox["\t", FontFamily->"Courier New"], StyleBox["abcacdcbcdcadbdcbdbabcbdcacbabdbabcabdadcdadbdcbd\[Dash]\n\t\t\t\ babdbcbacbcdbabdcdbdcacdbcbacbcdcacdcbdcdadbdcbca", FontFamily->"Courier New", FontWeight->"Bold"], "\n\t\nand let ", StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["x", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")) = ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["x", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")) for all ", FontFamily->"Times New Roman"], StyleBox["x", FontFamily->"Times New Roman", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`{a, b, c, d}\)]], ", where ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox[": ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[" ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[RightArrow] \)]], StyleBox[" ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[" is the letter-to-letter endomorphism that performs the cyclic \ permutation ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["a", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") = ", FontFamily->"Times New Roman"], StyleBox["b", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[", ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["b", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") = ", FontFamily->"Times New Roman"], StyleBox["c", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[", ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["c", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") = ", FontFamily->"Times New Roman"], StyleBox["d", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" and ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["d", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") = ", FontFamily->"Times New Roman"], StyleBox["a.", FontFamily->"Times New Roman", FontSlant->"Italic"], " ", StyleBox["Here | ", FontFamily->"Times New Roman"], StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["a", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") | = 98 and the Parikh vector of ", FontFamily->"Times New Roman"], StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["a", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") is ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[Psi]\)]], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["g", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FontFamily->"Times New Roman"], StyleBox["a", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")) = (18, 28, 27, 25). \n\t", FontFamily->"Times New Roman"], "One may check that, for this ", StyleBox["g", FontSlant->"Italic"], ", ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ")", StyleBox[" ", FontSlant->"Italic"], "is a-2-free for all a-2-free words ", StyleBox["w", FontSlant->"Italic"], " of length ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " 6 in ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], ", and for all a-2-free words ", StyleBox["w", FontSlant->"Italic"], " of length = 7, except for ", StyleBox["acad", FontSlant->"Italic"], StyleBox["bc", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["a", FontSlant->"Italic"], " and ", StyleBox["acad", FontSlant->"Italic"], StyleBox["cb", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["a", FontSlant->"Italic"], " and their cyclic permutations. This means that all words in the set\n\ \t\n(1)\tnot-a-2-free = \t", StyleBox["g", FontSlant->"Italic"], "({", StyleBox["acad", FontSlant->"Italic"], StyleBox["bc", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["bdbacdb", FontSlant->"Italic"], ", ", StyleBox["cacbdac", FontSlant->"Italic"], ", ", StyleBox["dbdcabd", FontSlant->"Italic"], "}) ", Cell[BoxData[ \(TraditionalForm\`\[Union]\)]], " \n \t \t\t", StyleBox["g", FontSlant->"Italic"], "({", StyleBox["acad", FontSlant->"Italic"], StyleBox["cb", FontSlant->"Italic", FontVariations->{"Underline"->True}], StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["bdbadcb", FontSlant->"Italic"], ", ", StyleBox["cacbadc", FontSlant->"Italic"], ", ", StyleBox["dbdcbad", FontSlant->"Italic"], "})\n\ncontain abelian squares. Thus ", StyleBox["g", FontSlant->"Italic"], " is not an a-2-free morphism of ", Cell[BoxData[ FormBox[ FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"], TraditionalForm]]], ".\n\tLet ", StyleBox["A", FontSlant->"Italic"], " = ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["a", FontSlant->"Italic"], "), ", StyleBox["B", FontSlant->"Italic"], " = ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["b", FontSlant->"Italic"], "), ", StyleBox["C", FontSlant->"Italic"], " = ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["c", FontSlant->"Italic"], "), ", StyleBox["D", FontSlant->"Italic"], " = ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["d", FontSlant->"Italic"], "), where ", StyleBox["g", FontSlant->"Italic"], " is as above. Using (1) and the fact concerning a-2-free words of length \ ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " 6, we conclude that all words obtained by any cyclic permutation from \ the words\n\n(2)\t", Cell[BoxData[ \(TraditionalForm\`A\+\[UnderBracket]\)], FontSize->18], StyleBox[" ", FontSize->24], Cell[BoxData[ \(TraditionalForm\`U\_1\)], FontSize->18], StyleBox[" ", FontSize->18], StyleBox["A", FontSize->18, FontSlant->"Italic"], StyleBox[" ", FontSize->18], Cell[BoxData[ \(TraditionalForm\`U\_2\)], FontSize->18], " ", Cell[BoxData[ \(TraditionalForm\`D\+\[UnderBracket]\)], FontSize->18], StyleBox[" ", FontSize->18], Cell[BoxData[ \(TraditionalForm\`V\_1\)], FontSize->18], " ", StyleBox["B", FontSize->18, FontSlant->"Italic"], StyleBox[" ", FontSize->18], Cell[BoxData[ \(TraditionalForm\`V\_2\)], FontSize->18], " ", StyleBox[" ", FontSize->18], Cell[BoxData[ \(TraditionalForm\`A\+\[UnderBracket]\)], FontSize->18], StyleBox[",", FontSize->18, FontSlant->"Italic"], "\t\twhere\t", Cell[BoxData[ \(TraditionalForm\`U\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`U\_2\)]], ", ", Cell[BoxData[ \(TraditionalForm\`V\_1\)]], ", ", Cell[BoxData[ \(TraditionalForm\`V\_2\)]], " are in ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], "),\n ", StyleBox[" ", FontSize->9], StyleBox[" ", FontSize->8], " |\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\ \[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]|\[Dash]\[Dash]\[Dash]\[Dash]\ \[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\[Dash]\ \[Dash]\[Dash]|\t\t\tand ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\)]], "(", Cell[BoxData[ \(TraditionalForm\`U\_1\)]], Cell[BoxData[ \(TraditionalForm\`U\_2\)]], ") = ", Cell[BoxData[ \(TraditionalForm\`\[Psi]\)]], "(", Cell[BoxData[ \(TraditionalForm\`V\_1\)]], Cell[BoxData[ \(TraditionalForm\`V\_2\)]], ")\n ", Cell[BoxData[ \(TraditionalForm\`P\_1\)]], " \t\t\t ", Cell[BoxData[ \(TraditionalForm\`P\_2\)]], "\n \ncontain abelian squares ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(P\_1\), "TraditionalForm"], \(P\_2\)}], TraditionalForm]]], " with starting and ending boundaries inside the underlined occurrences of \ words taken from {", StyleBox["A", FontSlant->"Italic"], ", ", StyleBox["B", FontSlant->"Italic"], ", ", StyleBox["C", FontSlant->"Italic"], ", ", StyleBox["D", FontSlant->"Italic"], "} as indicated in (2)." }], "Text"], Cell[TextData[{ "\tOn the other hand, it can be checked from the prefixes of the image \ words in ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], "), by using Carpi's algorithm, that the words of the form (2) and their \ cyclic permutations, are the only possible subwords in any ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") that contain abelian squares, provided that ", StyleBox["w", FontSlant->"Italic"], " in ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], " is a-2-free. Moreover, the coding properties of ", StyleBox["g", FontSlant->"Italic"], " guarantee that if, for any ", StyleBox["i ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " {0, 1, 2, 3}, \n\t\n\t", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["w", FontSlant->"Italic"], ") = ", StyleBox["P", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], "(", StyleBox["A", FontSlant->"Italic"], StyleBox[" ", FontSize->14], Cell[BoxData[ \(TraditionalForm\`U\_1\)]], " ", StyleBox["A", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`U\_2\)]], " ", StyleBox["D", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`V\_1\)]], " ", StyleBox["B", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`V\_2\)]], " ", StyleBox["A", FontSlant->"Italic"], ")", StyleBox[" S", FontSlant->"Italic"], ", with ", StyleBox["P", FontSlant->"Italic"], ", ", StyleBox["S", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ FormBox[ SuperscriptBox[ FormBox[\(\[CapitalSigma]\_4\), "TraditionalForm"], "*"], TraditionalForm]]], ", and ", Cell[BoxData[ \(TraditionalForm\`U\_\[Nu]\)]], ":s, ", Cell[BoxData[ \(TraditionalForm\`V\_\[Nu]\)]], ":s as in (2),\n\nthen ", StyleBox["w ", FontSlant->"Italic"], "can be factorized as follows:\n\n(3)\t", StyleBox["w", FontSlant->"Italic"], " = ", StyleBox["p ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], "(", StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], StyleBox["d ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_1\)]], StyleBox["b ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_2\)]], StyleBox["a", FontSlant->"Italic"], ")", StyleBox[" s", FontSlant->"Italic"], ", with ", StyleBox["P = g", FontSlant->"Italic"], "(", StyleBox["p", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`U\_1\)]], "= ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], "), ", Cell[BoxData[ \(TraditionalForm\`U\_2\)]], "= ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], "), ", Cell[BoxData[ \(TraditionalForm\`V\_1\)]], "= ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`v\_1\)]], "), ", Cell[BoxData[ \(TraditionalForm\`V\_2\)]], "= ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`v\_2\)]], "), ", StyleBox["S = g", FontSlant->"Italic"], "(", StyleBox["s", FontSlant->"Italic"], "),\n\t", StyleBox["g", FontSlant->"Italic"], "( ", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], ") = ", Cell[BoxData[ \(TraditionalForm\`U\_1\)]], " ", StyleBox["A", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`U\_2\)]], " and ", StyleBox["g", FontSlant->"Italic"], "(", Cell[BoxData[ \(TraditionalForm\`v\_1\)]], StyleBox["b ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_2\)]], ") = ", Cell[BoxData[ \(TraditionalForm\`V\_1\)]], " ", StyleBox["B", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`V\_2\)]], ".\n\t\nMoreover, ", StyleBox["g ", FontSlant->"Italic"], "is commutatively bijective, that is, the vectors ", Cell[BoxData[ \(TraditionalForm\`\[Psi](A)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Psi](B)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Psi](C)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\[Psi](D)\)]], " are linearly independent. This implies, together with (3) and the fact \ ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(U\_1\), "TraditionalForm"], FormBox[\(U\_2\), "TraditionalForm"]}], ")"}], " ", "=", " ", RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(V\_1\), "TraditionalForm"], FormBox[\(V\_2\), "TraditionalForm"]}], ")"}]}], TraditionalForm]]], ", that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(u\_1\), "TraditionalForm"], FormBox[\(u\_2\), "TraditionalForm"]}], ")"}], " ", "=", " ", RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(v\_1\), "TraditionalForm"], FormBox[\(v\_2\), "TraditionalForm"]}], ")"}]}], TraditionalForm]]], " in all the factorizations of ", StyleBox["w ", FontSlant->"Italic"], "in (3)." }], "Text"], Cell[TextData[{ "\tDefine the endomorphism ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_98\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\({a, b, c, d}\^*\)\)]], " ", Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\({a, b, c, d}\^*\)\)]], " by the productions:\n\n\t", Cell[BoxData[ FormBox[GridBox[{ { RowBox[{ StyleBox["a", FontSlant->"Italic"], " ", "\[Rule]", StyleBox["A", FontSlant->"Italic"]}]}, { RowBox[{ StyleBox["b", FontSlant->"Italic"], " ", "\[Rule]", StyleBox["D", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]]}]}, { RowBox[{ StyleBox["c", FontSlant->"Italic"], " ", "\[Rule]", StyleBox["C", FontSlant->"Italic"]}]}, { RowBox[{ StyleBox["d", FontSlant->"Italic"], " ", "\[Rule]", StyleBox["B", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]]}]} }], TraditionalForm]]], "\t\tor\t", Cell[BoxData[ FormBox[GridBox[{ { RowBox[{ StyleBox["a", FontSlant->"Italic"], " ", "\[Rule]", \(\(\[Sigma]\^i\)(A)\)}]}, { RowBox[{ StyleBox["b", FontSlant->"Italic"], " ", "\[Rule]", RowBox[{\(\[Sigma]\^i\), "(", StyleBox["D", FontSlant->"Italic"], StyleBox[")", FontSlant->"Italic"]}]}]}, { RowBox[{ StyleBox["c", FontSlant->"Italic"], " ", "\[Rule]", RowBox[{\(\[Sigma]\^i\), "(", StyleBox["C", FontSlant->"Italic"], StyleBox[")", FontSlant->"Italic"]}]}]}, { RowBox[{ StyleBox["d", FontSlant->"Italic"], " ", "\[Rule]", RowBox[{\(\[Sigma]\^i\), "(", StyleBox["B", FontSlant->"Italic"], StyleBox[")", FontSlant->"Italic"]}]}]} }], TraditionalForm]]], " , \twhere ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is a cyclic permutation and ", StyleBox["i", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " {1,2,3}.\n\t" }], "Text"], Cell[TextData[{ "Now it follows from above that all words ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", StyleBox["w", FontSlant->"Italic"], ") are a-2-free, whenever ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], " is a-2-free and does not have, for any ", StyleBox["i", FontSlant->"Italic"], ",", StyleBox[" ", FontSlant->"Italic"], " a subword of the form \n\n(4)\t", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], " (", StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], StyleBox["b", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_1\)]], StyleBox["d", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_2\)]], StyleBox["a", FontSlant->"Italic"], ")", StyleBox[" ", FontSlant->"Italic"], "with ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(u\_1\), "TraditionalForm"], FormBox[\(u\_2\), "TraditionalForm"]}], ")"}], " ", "=", " ", RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(v\_1\), "TraditionalForm"], FormBox[\(v\_2\), "TraditionalForm"]}], ")"}]}], TraditionalForm]]], "; ", StyleBox["i = ", FontSlant->"Italic"], "0, 1, 2, 3.", StyleBox["\n", FontSlant->"Italic"], " " }], "Text"], Cell[TextData[{ "\tIndeed, it turns out that no subword of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["w", FontSlant->"Italic"], ") or ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", StyleBox["w", FontSlant->"Italic"], ") can be of the form (4), for any a-2-free ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], ". This can be checked by modifying Carpi's algorithm, see Proposition 1, \ for prefixes of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], ") and ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], "). In order to illustrate this modified, and also the original Carpi's \ algorithm, that is, part (iii) in Proposition 1, we consider the following. \ Let | mark the boundaries of the blocks of imagewords of ", StyleBox["X ", FontSlant->"Italic"], ", ", StyleBox["Y", FontSlant->"Italic"], ", ", StyleBox["Z", FontSlant->"Italic"], " in {", StyleBox["A", FontSlant->"Italic"], ", ", StyleBox["B", FontSlant->"Italic"], ", ", StyleBox["C", FontSlant->"Italic"], ", ", StyleBox["D", FontSlant->"Italic"], "}. In the case of \n\t\n\t", StyleBox["X ", FontSlant->"Italic"], "| ", StyleBox["Y ", FontSlant->"Italic"], "| ", StyleBox["Z", FontSlant->"Italic"], " = ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(p\_0\), "TraditionalForm"], \(s\_0\)}], TraditionalForm]]], "| ", Cell[BoxData[ \(TraditionalForm\`\(p\_1\) s\_1\)]], "| ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(p\_2\), "TraditionalForm"], \(s\_2\)}], TraditionalForm]]], " = ", Cell[BoxData[ \(TraditionalForm\`p\_0\)]], " ", StyleBox["u v", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`s\_2\)]], "; with ", StyleBox["u", FontSlant->"Italic"], " = ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(s\_0\), "TraditionalForm"], \(p\_1\)}], TraditionalForm]]], ", ", StyleBox["v", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\(s\_1\) p\_2\)\)\)]], ", ", StyleBox["uv", FontSlant->"Italic"], " as an abelian square; \n\t \nwe have ", Cell[BoxData[ \(TraditionalForm\`p\_0\)]], " = pref(", StyleBox["X", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`s\_0\)]], " = suff(", StyleBox["X", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`p\_1\)]], " = pref(", StyleBox["Y", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`s\_1\)]], " = suff(", StyleBox["Y", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`p\_2\)]], " = pref(", StyleBox["Z", FontSlant->"Italic"], "), ", Cell[BoxData[ \(TraditionalForm\`s\_2\)]], " = suff(", StyleBox["Z", FontSlant->"Italic"], "). Thus\n\n(5)\t", Cell[BoxData[ \(TraditionalForm\`0\)]], " = ", Cell[BoxData[ \(TraditionalForm\`\(\[Psi](v)\)\ \[Dash]\ \(\[Psi](u)\)\)]], " \n\t = ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(\(s\_1\) p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[ RowBox[{ FormBox[\(s\_0\), "TraditionalForm"], \(p\_1\)}], "TraditionalForm"], ")"}]}], TraditionalForm]]], " \n\t = ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(s\_1\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[\(s\_0\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}], " "}]}], TraditionalForm]]], "\n\t = ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", RowBox[{\(\[Psi](Y)\), " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", RowBox[{"(", RowBox[{\(\[Psi](X)\), " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}]}], ")"}], " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}], " "}]}], TraditionalForm]]], "\n\t = ", Cell[BoxData[ FormBox[ RowBox[{\(\(\[Psi](Y)\)\ \[Dash]\ \(\[Psi](X)\)\), " ", "+", " ", RowBox[{"(", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], ")"}]}], TraditionalForm]]], "\n\nSince ", Cell[BoxData[ \(TraditionalForm\`\(\[Psi](v)\)\ \[Dash]\ \(\[Psi](u)\)\)]], " = ", Cell[BoxData[ \(TraditionalForm\`0\)]], ", for an abelian square ", StyleBox["uv", FontSlant->"Italic"], ", Carpi's idea in Proposition 1 (iii) is to test whether the linear \ combinations of the Parikh vectors of prefixes, i.e., ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], TraditionalForm]]], " belong to ", Cell[BoxData[ \(TraditionalForm\`G\_h\)]], " (the subgroup of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\^\[CapitalSigma]\)]], " generated by ", Cell[BoxData[ FormBox[ RowBox[{"\[Psi]", "(", RowBox[{"h", "(", FormBox[\(\[CapitalSigma]\_4\), "TraditionalForm"], ")"}], ")"}], TraditionalForm]]], ", where ", StyleBox["h ", FontSlant->"Italic"], " is the morphism to be tested). In (2) we had ", StyleBox["X", FontSlant->"Italic"], " ", StyleBox["=", FontSlant->"Italic"], " ", StyleBox["A", FontSlant->"Italic"], ",", StyleBox[" ", FontSize->14], StyleBox["Y", FontSlant->"Italic"], " = ", StyleBox["D", FontSlant->"Italic"], ", ", StyleBox["Z ", FontSlant->"Italic"], "=", StyleBox[" A. \n\t", FontSlant->"Italic"], "Corresponding to the search of the subword pattern ", StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], StyleBox["b", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_1\)]], StyleBox["d", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_2\)]], StyleBox["a", FontSlant->"Italic"], ", ", StyleBox[" ", FontSlant->"Italic"], "with ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(u\_1\), "TraditionalForm"], FormBox[\(u\_2\), "TraditionalForm"]}], ")"}], " ", "=", " ", RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(v\_1\), "TraditionalForm"], FormBox[\(v\_2\), "TraditionalForm"]}], ")"}]}], TraditionalForm]]], ", and the natural cyclic permutations in (4), we denote ", StyleBox["u = a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_1\)]], StyleBox["a", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\`u\_2\)]], StyleBox["b", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], ", ", StyleBox["v", FontSlant->"Italic"], " = ", Cell[BoxData[ \(TraditionalForm\`v\_1\)]], StyleBox["d", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`v\_2\)]], StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["x", FontSlant->"Italic"], " = ", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["left", FontSlant->"Italic"], " = ", StyleBox["a", FontSlant->"Italic"], ", ", StyleBox["y", FontSlant->"Italic"], " = ", StyleBox["b", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], ", ", StyleBox["right", FontSlant->"Italic"], " = ", StyleBox["d", FontWeight->"Bold", FontSlant->"Italic", FontColor->RGBColor[1, 0, 0]], ", ", StyleBox["z", FontSlant->"Italic"], " = ", StyleBox["a", FontSlant->"Italic"], " (we exclude the natural cyclic permutations for simplicity). From this, \ and (5), i.e., from ", Cell[BoxData[ \(TraditionalForm\`\(\[Psi](v)\)\ \[Dash]\ \(\[Psi](u)\)\)]], " = ", Cell[BoxData[ FormBox[ RowBox[{\(\(\[Psi](Y)\)\ \[Dash]\ \(\[Psi](X)\)\), " ", "+", " ", RowBox[{"(", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], ")"}]}], TraditionalForm]]], ", we obtain\n\n(6)\t", Cell[BoxData[ \(TraditionalForm\`0\)]], " = ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(v\_1\), "TraditionalForm"], FormBox[\(v\_2\), "TraditionalForm"]}], ")"}], " ", "\[Dash]", " ", RowBox[{"\[Psi]", "(", RowBox[{ FormBox[\(u\_1\), "TraditionalForm"], FormBox[\(u\_2\), "TraditionalForm"]}], ")"}]}], TraditionalForm]]], " \n\t = ", Cell[BoxData[ \(TraditionalForm\`\((\(\[Psi](v)\)\ \[Dash]\ \(\[Psi]( z)\)\ \[Dash]\ \(\[Psi](right)\))\)\ \[Dash]\ \((\(\[Psi]( u)\)\ \[Dash]\ \(\[Psi](xy)\)\ \[Dash]\ \(\[Psi]( left)\))\)\)]], " \n\t = ", Cell[BoxData[ FormBox[ RowBox[{\(\(\[Psi](Y)\)\ \[Dash]\ \(\[Psi](X)\)\), " ", "+", " ", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], ")"}], " ", "\[Dash]", " ", \(\[Psi](z)\)}], " ", "+", " ", \(\(\[Psi](xy)\)\ \[Dash]\ \(\[Psi](right)\)\), " ", "+", " ", \(\[Psi](left)\)}], TraditionalForm]]], "\n\nThus, instead of testing whether ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], " ", "\[Element]", " ", FormBox[\(G\_\(g\_98\)\), "TraditionalForm"]}], TraditionalForm]]], " we now test whether ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_0\), "TraditionalForm"], ")"}], " ", "+", " ", RowBox[{ RowBox[{"\[Psi]", "(", FormBox[\(p\_2\), "TraditionalForm"], ")"}], " ", "\[Dash]", " ", "2", " ", RowBox[{"\[Psi]", "(", FormBox[\(p\_1\), "TraditionalForm"], ")"}]}]}], ")"}], " ", "\[Dash]", " ", \(\[Psi](z)\)}], " ", "+", " ", \(\(\[Psi](xy)\)\ \[Dash]\ \(\[Psi](right)\)\), " ", "+", " ", \(\[Psi](left)\)}], " ", "\[Element]", " ", FormBox[\(G\_\(g\_98\)\), "TraditionalForm"]}], TraditionalForm]]], ". When programming this test for a computer, it is best to include the \ first letter of ", StyleBox["u", FontSlant->"Italic"], ", i.e. ", StyleBox["x", FontSlant->"Italic"], " (above ", StyleBox["x", FontSlant->"Italic"], " = ", StyleBox["a", FontSlant->"Italic"], ") as the last letter of ", Cell[BoxData[ \(TraditionalForm\`p\_0\)]], " to reduce the number of prefixes to be tested. Of course, it is possible \ to speed the computation even more, in a similar fashion, for other letters \ as well, if necessary. \n\tThe short image words ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", StyleBox["w", FontSlant->"Italic"], "), for words ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], " of length 2, were in turn tested with the following simple pattern \ matching ", StyleBox["Mathematica", FontSlant->"Italic"], " program which works fast enough for words up to length 300 or so. In the \ pattern matching part, we do not use many subpatterns, otherwise the \ computation time may become too long for practical purposes. Below the \ function ", StyleBox["s", FontFamily->"Courier New", FontWeight->"Bold"], " is the same as ", StyleBox["myParikh", FontFamily->"Courier New", FontWeight->"Bold"], " defined in Section 3." }], "Text"], Cell[BoxData[{ \(\(Clear[myPatterns];\)\), "\n", \(myPatterns[ x_String] := \[IndentingNewLine]Module[{pattString = {}}, \ \[IndentingNewLine]Characters[ x] /. {___, "\", w1__, "\", w2__, "\", ___} \[RuleDelayed] q /; If[s[{w1}] - "\" === s[{w2}] - "\", pattString = Append[pattString, StringJoin["\", w1, "\", w2, "\"]]]; pattString]\)}], "Input"], Cell[TextData[{ "\n\tBecause all the tests mentioned above show that no subword of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], "(", StyleBox["w", FontSlant->"Italic"], ") or ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "(", StyleBox["w", FontSlant->"Italic"], ") is of the form (4), for any a-2-free ", Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], ", we now draw the conclusion: \n\n", StyleBox["Proposition 2.", FontWeight->"Bold"], " All words of the form ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(h\_k\), "TraditionalForm"], "\[CenterEllipsis]", " ", FormBox[\(h\_1\), "TraditionalForm"]}], TraditionalForm]]], "(", StyleBox["w", FontSlant->"Italic"], "), where ", Cell[BoxData[ \(TraditionalForm\`h\_1\)]], ", ... , ", Cell[BoxData[ \(TraditionalForm\`h\_k\)]], " are of the form ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], ") or ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "); ", StyleBox["i ", FontSlant->"Italic"], "= 0,1,2,3; are a-2-free, provided that ", StyleBox["w", FontSlant->"Italic"], " is a-2-free and does not contain a subword of the form (4) in the case \ of ", Cell[BoxData[ \(TraditionalForm\`h\_1\)]], " = ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\^i\)]], "(", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], "). ", Cell[BoxData[ \(TraditionalForm\`\[Square]\)]], "\n\n\tThus, instead of a single endomorphism we can now iterate several \ endomorphisms and obtain completely new infinite a-2-free words and \ D0L-sequences over four letters. Note that in Proposition 2 one can choose as \ morphisms ", Cell[BoxData[ \(TraditionalForm\`h\_i\)]], " all cyclic permutations of ", Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], " but not all permutations in general.\n\tAs mentioned in Section 2, the \ languages of the form ", Cell[BoxData[ FormBox[ RowBox[{ FormBox[\(h\_k\), "TraditionalForm"], "\[CenterEllipsis]", " ", FormBox[\(h\_1\), "TraditionalForm"]}], TraditionalForm]]], "(", StyleBox["w", FontSlant->"Italic"], "), obtained by using compositions of morphims, are called DT0L-languages. \ See [32] for more details. \n\t" }], "Text"], Cell[TextData[{ StyleBox["7 Extensive computer aided searches\n", FontWeight->"Bold"], "\n", StyleBox["We have checked very nearly all the possibilites in the size \ range ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], StyleBox[" ", FontFamily->"Times New Roman"], "4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], StyleBox["100 for those endomorphisms ", FontFamily->"Times New Roman"], StyleBox["g ", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["of ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[", the", FontFamily->"Times New Roman"], " words ", Cell[BoxData[ \(TraditionalForm\`g\)]], "(", StyleBox["x", FontSlant->"Italic"], "), ", StyleBox["x", FontSlant->"Italic"], " ", Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], " ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], ", of which are obtained by cyclically permutating the letters in ", Cell[BoxData[ \(TraditionalForm\`g\)]], "(", StyleBox["a", FontSlant->"Italic"], "). Moreover, there is no need for any long computations anymore (in \ checking the remaining few chances), since all possible candidates for image \ words have already been constructed. The result is ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " almost certainly ", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], " as follows: e", StyleBox["xcluding symmetry (mirror images, cyclic permutations, or \ renaming letters), there are no other cyclic endomorphisms of ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[" in the size range ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], StyleBox[" ", FontFamily->"Times New Roman"], "4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], StyleBox["100, except ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], ", ", StyleBox[" that are ", FontFamily->"Times New Roman"], "a-2-free", StyleBox[" or generate ", FontFamily->"Times New Roman"], "a-2-free", StyleBox[" L-sequences. \n\tWe have also tried many other approaches in \ which the endomorphisms are not growing uniformly. For example, i", FontFamily->"Times New Roman"], StyleBox["n the following cases of ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" of ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[", and in thousands other (larger) cases as well, ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") is ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" for all ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[Element] \)]], StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_3\^*\)\)]], StyleBox["= ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\({a, b, c}\^*\)\)], FontFamily->"Times New Roman"], StyleBox[". However, no proper ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["d", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") exists for any of the triplets ", FormatType->StandardForm, FontFamily->"Times New Roman"], "{ ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["a", FontSlant->"Italic"], "), ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["b", FontSlant->"Italic"], "), ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["c", FontSlant->"Italic"], ") }", StyleBox[":", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["\n\n13 13 8\t\t\t15 15 9\t\t\t15 15 25\na ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abacabadacdbd\t\ta ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abacadabdadcdbd\ta ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abcdbcacbdcdadb\nb ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" acdcbcacbcdbd\t\tb ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abacadcbcadcdbd\tb ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abcbdbadbdcdadb\nc ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abdbcdbd\t\t\tc ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" abdbcbabd\t\tc ", FormatType->StandardForm, FontFamily->"Arial"], Cell[BoxData[ \(TraditionalForm\` \[Rule] \)]], StyleBox[" adacadabacbcdcadabacabadb\n\n", FormatType->StandardForm, FontFamily->"Arial"], StyleBox["Here we firstly fixed ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["a", FontSlant->"Italic"], ")", StyleBox[" and ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["b", FontSlant->"Italic"], "), and then started to search for suffix-prefix pairs (", StyleBox["suff", FontSlant->"Italic"], ", ", StyleBox["pref", FontSlant->"Italic"], ") for ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["c", FontSlant->"Italic"], ")", StyleBox[" and ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["d", FontSlant->"Italic"], "). In this setting, all words of the form ", StyleBox["suff", FontSlant->"Italic"], " ", StyleBox["w", FontSlant->"Italic"], " ", StyleBox["pref", FontSlant->"Italic"], ", where ", StyleBox["w", FontSlant->"Italic"], " \[Element] {", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["a", FontSlant->"Italic"], "),", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["b", FontSlant->"Italic"], ")", StyleBox["}", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\^n\)]], "; with ", StyleBox["n", FontSlant->"Italic"], " = 0,1,2,3; have to be a-2-free.", StyleBox["\n\t", FormatType->StandardForm, FontFamily->"Arial"], StyleBox["Moreover, we now know of over 90 different cases of ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g ", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["of ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[", for which ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") is ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" for every ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^4\), "TraditionalForm"]}], TraditionalForm]]], StyleBox["= ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`{a, b, c, d}\^4\)]], StyleBox[" (i.e. for ", FontFamily->"Times New Roman"], StyleBox["w", FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" of length = 4) ", FontFamily->"Times New Roman"], StyleBox["but not for all ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^5\), "TraditionalForm"]}], TraditionalForm]]], StyleBox[". ", FormatType->StandardForm, FontFamily->"Arial"], StyleBox["Some endomorphisms (of size ", FormatType->StandardForm, FontFamily->"Times New Roman"], "4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], StyleBox["98", FontFamily->"Times New Roman"], StyleBox[" and ", FormatType->StandardForm, FontFamily->"Times New Roman"], "4", Cell[BoxData[ \(TraditionalForm\`\[Times]\)]], StyleBox["100", FontFamily->"Times New Roman"], StyleBox[") are even ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" for every ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^6\), "TraditionalForm"]}], TraditionalForm]]], " ", StyleBox["but not for all ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^7\), "TraditionalForm"]}], TraditionalForm]]], ".", StyleBox[" Thus, we have examples of endomorphisms ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["of ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], ",", StyleBox[" each of which produce thousands of ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" words of length ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` \[GreaterEqual] \)]], StyleBox[" 600 (some words being much longer), but still fail to be useful \ in our search for new", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox[" ", FontFamily->"Times New Roman"], StyleBox["endomorphisms generating a-2-free L-sequences ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["on ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_4\)]], StyleBox[". ", FormatType->StandardForm, FontFamily->"Times New Roman"], "\n\tIn one setting, we let ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["a", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " and ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["b", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " be fixed from the set {", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], "), ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["b", FontSlant->"Italic"], "), ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["c", FontSlant->"Italic"], ")}, and then checked different possibilities for the remaining ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["c", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " and ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["d", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], ". Here we separated two cases as follows:\n\nCase 1. ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["a", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") ", FormatType->StandardForm, FontFamily->"Times New Roman"], "= ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], "), ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["b", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " = ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["b", FontSlant->"Italic"], "), 1 ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\` | \)]], " ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["c", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` | \)]], " ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " 85, 1 ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\` | \)]], " ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["d", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\` | \)]], " \[LessEqual] 120 (we had to abort this run)\nCase 2. ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["a", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " = ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["a", FontSlant->"Italic"], "), ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["b", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " = ", StyleBox["g", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\_85\)]], "(", StyleBox["c", FontSlant->"Italic"], "), 1 ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\` | \)]], " ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["c", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\` | \)]], " ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " 90, 1 ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " ", Cell[BoxData[ \(TraditionalForm\` | \)]], " ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["d", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\` | \)]], " \[LessEqual] 120 (this checking was relatively fast)\n\nFirstly, we \ searched through all possibilities for ", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["c", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") in the range mentioned above. In more detail, we went through \ all triplets { ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["a", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["), ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["b", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["), ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["c", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") } such that ", FormatType->StandardForm, FontFamily->"Times New Roman"], " ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") is ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" for all ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_3\^*\), "TraditionalForm"]}], TraditionalForm]]], StyleBox["= ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\({a, b, c}\^*\)\)], FontFamily->"Times New Roman"], " (here ", StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], " is of length ", Cell[BoxData[ \(TraditionalForm\` \[LessEqual] \)]], " 7), and ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[")", FormatType->StandardForm, FontFamily->"Times New Roman"], " can be extended to the right with a proper prefix of ", StyleBox["g", FontSlant->"Italic"], "(", StyleBox["d", FontSlant->"Italic"], ") of length 20 or so. Excluding all symmetrical cases, we found \ thousands of different triplets. However, one can check that no proper ", StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["d", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") can be found for any of them, though, in this setting, we \ found over 20 cases of ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[", for which ", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["g", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox["(", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox["w", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[") is ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" for every ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free", StyleBox[" word", FormatType->StandardForm, FontFamily->"Times New Roman"], StyleBox[" ", FormatType->StandardForm, FontFamily->"Times New Roman", FontSlant->"Italic"], StyleBox[" ", FontFamily->"Times New Roman"], Cell[BoxData[ FormBox[ RowBox[{"w", " ", "\[Element]", " ", FormBox[\(\[CapitalSigma]\_4\^*\), "TraditionalForm"]}], TraditionalForm]]], StyleBox[" of length = 4. It is very counterintuitive fact that in Case 1 \ (with ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\(1\)\(\ \)\(\[LessEqual]\)\)\ | \ g(c)\ | \ \(\(\[LessEqual]\)\(\ \)\(85\)\)\)]], StyleBox["), when searching for ", FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["d", FontSlant->"Italic"], ")", StyleBox[", the computation time was over 10 times longer than in Case 2 \ (with ", FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`\(\(1\)\(\ \)\(\[LessEqual]\)\)\ | \ g(c)\ | \ \(\(\[LessEqual]\)\(\ \)\(90\)\)\)]], StyleBox[") ! Even though it is by no means the first time that such a ", FontFamily->"Times New Roman"], "complex non-linear behaviour", StyleBox[" occurs in our search for strings (timewise or spacewise, and in \ much shorter and carefully rechecked runs), we plan to recheck Case 1, and \ maybe extend it, in the near future. Nevertheless, the result file indicates \ that most likely all possibilities for ", FontFamily->"Times New Roman"], StyleBox["g", FontSlant->"Italic"], "(", StyleBox["d", FontSlant->"Italic"], ") were checked already, though the process remained active", StyleBox[". Indeed, it seems that sometimes operating systems can cause \ problems in runs that may take months to complete. For the Cases 1 and 2, we \ used C++ on a two processor ", FontFamily->"Times New Roman"], "400 MHz PC running Linux.\n\tIn conclusion, we are not very optimistic \ that", StyleBox[" in the near future it would be possible to find more examples of \ ", FormatType->StandardForm, FontFamily->"Times New Roman"], "abelian squar", StyleBox["e-free", FontFamily->"Times New Roman"], StyleBox[" endomorphisms, substitutions, or L-sequences ", FormatType->StandardForm, FontFamily->"Times New Roman"], "of ", Cell[BoxData[ \(TraditionalForm\`\(\[CapitalSigma]\_4\^*\)\)]], StyleBox[" which would not be based on the structures of ", FormatType->StandardForm, FontFamily->"Times New Roman"], Cell[BoxData[ \(TraditionalForm\`g\_85\)]], " or ", Cell[BoxData[ \(TraditionalForm\`g\_98\)]], ".\n\t\t\t" }], "Text", TextAlignment->Left, TextJustification->1], Cell[TextData[{ StyleBox["8 Open problems (by ", FontWeight->"Bold"], StyleBox["Sami M\[ADoubleDot]kel\[ADoubleDot], University of Turku", FontFamily->"Times New Roman", FontWeight->"Bold"], StyleBox[") ", FontWeight->"Bold"], "\n\n", StyleBox["Problem 1.", FontWeight->"Bold"], " Can you avoid abelian squares of the form ", StyleBox["uv,", FontSlant->"Italic"], " where ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(u\)\(|\)\(\ \)\(\(\[GreaterEqual]\)\(\ \ \)\(2\)\)\)\)]], ", over three letters? \[Dash] Computer experiments show that you can \ avoid these patterns at least in words of length 450. \n", StyleBox["Problem 2.", FontWeight->"Bold"], " Can you avoid abelian cubes of the form ", StyleBox["uvw,", FontSlant->"Italic"], " where ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(u\)\(|\)\(\ \)\(\(\[GreaterEqual]\)\(\ \ \)\(2\)\)\)\)]], ", over two letters? \[Dash] You can do this at least for words of length \ 250.\n" }], "Text"], Cell[TextData[{ StyleBox["9 Material on the Internet\n", FontWeight->"Bold"], "\nWe plan to place C/C++ programs and a great number of result files from \ our long computer runs at ", StyleBox[ButtonBox["http://south.rotol.ramk.fi", ButtonData:>{ URL[ "http://south.rotol.ramk.fi"], None}, ButtonStyle->"Hyperlink"], FontVariations->{"Underline"->True}], " in the near future. This material would provide a pool of long a-2-free \ strings over 4 letters for possible further investigations. As mentioned in \ Section 7, some of the endomorphisms are a-2-free", StyleBox[" for every ", FormatType->StandardForm, FontFamily->"Times New Roman"], "a-2-free words of length up to 6.\n\tFrom ", StyleBox["http://south.rotol.ramk.fi/~keranen/Forssa/UsingTheEmptySet.html", FontVariations->{"Underline"->True}], " (", StyleBox[".nb", FontVariations->{"Underline"->True}], ") the reader may find examples of computer algebra programs in which we \ pay special attention to handling the empty set. Indeed, in our study, the \ empty set (or the empty word) is many times a natural starting point, and \ the", StyleBox[" ", FontFamily->"Verdana", FontSize->9, FontSlant->"Italic"], "meticulous use of it supports us to keep the programs clear and reliable. \ In many cases the computation also ends with the empty set as a result. For \ example, the reader may try the following ", StyleBox["Mathematica", FontSlant->"Italic"], " program which starts, in a sense, from {{}} and ends with {}:" }], "Text"], Cell[BoxData[ \(With[{n = 8, k = 3}, NestList[DeleteCases[ Flatten[Map[Table[Append[#, i - 1], {i, k}] &, #], 1], {___, u__, v__} /; Sort[{u}] \[Equal] Sort[{v}]]\ &, {{}}, n]]\)], "Input"], Cell["\<\ Indeed, this computation shows that abelian squares are unavoidable \ over 3 letters, since every word of length 8 turns out to contain them. \ Originally, this style of programming arose in discussions with Stephen \ Wolfram, and our program above is a modified version of the example that \ Wolfram presents in [35, p.944]. \ \>", "Text"], Cell[TextData[{ StyleBox["Acknowledgements", FontWeight->"Bold"], "\nWe gratefully acknowledge the participation of the following individuals \ most of who have been students at the Rovaniemi Polytechnic over the course \ of this study from 1990 to 2003. These people have made a number of computer \ programs for searching strings with desirable properties, or helped in a \ crucial way to set up the computing environments. Starting year is given in \ parenthesis: Kari Tuovinen (1990); Minna Iivonen, Anja Keskinarkaus, Marko \ Manninen (1993); Abdeljalil Chabani, Tomi Laakso (1994); Mika Moilanen, Juha \ S\[ADoubleDot]rest\[ODoubleDot]niemi (1996); Juho Alfthan (1999); Olli-Pentti \ Saira (2000); Marja Kentt\[ADoubleDot], Ville Mattila (2001); Lauri Autio, \ and Marianna M\[ODoubleDot]ll\[ADoubleDot]ri (2002). \n\tOver the years we \ have extensively used many computers at the School of Technology, Rovaniemi \ Polytechnic, and quite recently also at the Art and Design Faculty of the \ University of Lapland. We wish to thank these institutions for allocating \ computational resources at our disposal.\n\t" }], "Text"], Cell[TextData[{ StyleBox["References\n", FontWeight->"Bold"], "[1]", StyleBox[" ", FontWeight->"Bold"], "S.I. Adjan. Burnside groups of odd exponent and irreducible systems of \ group identities. In W.W. Boone et al., editors, Word Problems, 19", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "37. North-Holland, Amsterdam, 1973.\n[2]", StyleBox[" ", FontWeight->"Bold"], "S.V. Avgustinovich and A.E. Frid. Words avoiding abelian inclusions. To \ appear in J. Automata, Languages and Combinatorics. Otto-von-Guericke-Univ., \ Magdeburg.\n[3]", StyleBox[" ", FontWeight->"Bold"], "J. Berstel. Some recent results on square-free words. In M. Fontet and K. \ Melhorn, editors, Proc. STACS '84, Lecture Notes in Comp. Sci., 166:14", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "25. Springer-Verlag, Berlin, 1984.\n[4] A. Carpi. On abelian power-free \ morphisms. Int. J. Algebra Comput., 3:151", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "167. World Sci. Publ. Company, 1993.\n[5] A. Carpi. On the number of \ abelian square-free words on four letters. Discrete Appl. Math., 81:155", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "167. Elsevier, 1998.\n[6] A. Carpi. On abelian squares and substitutions. \ Theor. Comp. Sci., 218:61", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "81. Elsevier, 1999.\n[7]", StyleBox[" ", FontWeight->"Bold"], "R. Cori and M.R. Formisano. Partially abelian square-free words. RAIRO \ Inform. Th\[EAcute]or. et Appl., 24:509", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "520, 1990.\n[8]", StyleBox[" ", FontWeight->"Bold"], "M. Crochemore. Sharp characterizations of square-free morphisms. Theoret. \ Comp. Sci., 18:221", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "226, 1982.\n[9]", StyleBox[" ", FontWeight->"Bold"], "J. Currie. Open problems in pattern avoidance. American Mathematical \ Monthly, 100:790", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "793, 1993.\n[10]", StyleBox[" ", FontWeight->"Bold"], "F.M. Dekking. Strongly non-repetitive sequences and progression-free sets. \ J. Combin. Theory Ser. A, 27:181", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "185, 1979.\n[11]", StyleBox[" ", FontWeight->"Bold"], "V. Dickert. Research topics in the theory of free partially commutative \ monoids. Bull. Europ. Assoc. Theoret. Comp. Sci., 40:479", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "491, 1990.\n[12]", StyleBox[" ", FontWeight->"Bold"], "R.C. Entringer and D.E. Jackson and J.A. Schatz. On non-repetitive \ sequences. J. Combin. Theory Ser. A, 16:159", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "164, 1974.\n[13]", StyleBox[" ", FontWeight->"Bold"], "P. Erd\[ODoubleDot]s. Some unsolved problems. Magyar Tud. Akad. Mat. Kutat\ \[OAcute] Int. K\[ODoubleDot]zl., 6:221", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "254, 1961.\n[14]", StyleBox[" ", FontWeight->"Bold"], "A.E. Frid. On the frequency of factors in a DOL word. J. Automata, \ Languages and Combinatorics, 3(1):29", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "41. Otto-von-Guericke-Univ., Magdeburg, 1998.\n[15]", StyleBox[" ", FontWeight->"Bold"], "G.A. Hedlund. Remarks on the work of Axel Thue on sequences. Nordisk Mat. \ Tidskr., 15:148", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "150, 1967.\n[16]", StyleBox[" ", FontWeight->"Bold"], "J. Justin and G. Pirillo and S. Varricchio. Unavoidable regularities and \ finiteness conditions for semigroups. In A. Bertoni and C. Bohm and P. \ Miglioli, editors, Proc. 3rd Italian Conf. on Theoret. Comp. Sci. '89, 350", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "355. World Scientific, Singapore, 1989.\n[17]", StyleBox[" ", FontWeight->"Bold"], "V. Ker\[ADoubleDot]nen. On the k-Freeness of Morphisms on Free Monoids. \ Annales Academi\[AE] Scientiarum Fennic\[AE], Ser. A. I. Mathematica \ Dissertationes, 61, 55 pages. Finnish Science Academy, 1986. \n[18]", StyleBox[" ", FontWeight->"Bold"], "V. Ker\[ADoubleDot]nen. On the k-freeness of morphisms on free monoids. In \ F.J. Brandenburg and G. Vidal-Naquet and M. Wirsing, editors, Proc. STACS \ '87, Lecture Notes in Comp. Sci., 247:180", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "188. Springer-Verlag, Berlin, 1987.\n[19] V. Ker\[ADoubleDot]nen. Abelian \ squares are avoidable on 4 letters. In W. Kuich, editor, Proc. ICALP '92, \ Lecture Notes in Comp. Sci., 623:41", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "52. Springer-Verlag, Berlin, 1992.\n[20] V. Ker\[ADoubleDot]nen. \ Mathematica", StyleBox[" ", FontSlant->"Italic"], "in research of avoidable patterns in strings, In V. Ker\[ADoubleDot]nen \ and P.Mitic, editors, Mathematics with Vision, Proc. First International \ Mathematica Symposium (IMS '95, Southampton, England), 259", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "266. Computational Mechanics Publications, 1995.\n[21] V. \ Ker\[ADoubleDot]nen. The avoidability of regularities in strings (in \ Finnish). Arkhimedes, 47(1):71", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "79, 1995", StyleBox[".", FontWeight->"Bold"], "\n[22] V. Ker\[ADoubleDot]nen. On abelian repetition-free words. In V. \ Demidov, editor, Proc. IAS '96, 8", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "14. Murmansk State Pedagogical Institute, Murmansk, 1996.\n[23]", StyleBox[" ", FontWeight->"Bold"], "V. Ker\[ADoubleDot]nen. Repetition-free strings and computer algebra (in \ Finnish). In C. Gefwert and P. Orponen and J. Sepp\[ADoubleDot]nen, editors, \ Logic, Mathematics and the Computer, Proc. Finnish Artificial Intelligence \ Society, 14:250", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "257. Hakapaino, Helsinki, 1996.\n[24]", StyleBox[" ", FontWeight->"Bold"], "T. Laakso. Musical rendering of an infinite repetition-free string. In C. \ Gefwert and P. Orponen and J. Sepp\[ADoubleDot]nen, editors, Logic, \ Mathematics and the Computer, Proc. Finnish Artificial Intelligence Society, \ 14:292", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "297. Hakapaino, Helsinki, 1996.\n[25]", StyleBox[" ", FontWeight->"Bold"], "M. Leconte. A characterization of power-free morphisms. Theoret. Comp. \ Sci., 38:117", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "122, 1985.\n[26]", StyleBox[" ", FontWeight->"Bold"], "M. Leconte. Kth power-free codes. In M. Nivat and D. Perrin, editors, \ Proc. Automata on Infinite Words '84, Lecture Notes in Comp. Sci., 192:172", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "187. Springer-Verlag, Berlin, 1985.\n[27]", StyleBox[" ", FontWeight->"Bold"], "M. Lothaire. Combinatorics on Words. Addison-Wesley, Reading, \ Massachusetts, 1983.\n[28] V. Mattila. Creating Permutation Repetition-Free \ Words and Testing Permutation Repetition-Freeness of Morphisms (in Finnish). \ B.Sc. Thesis. Rovaniemi Polytechnic, 2002.\n[29] S. M\[ADoubleDot]kel\ \[ADoubleDot]. Patterns in Words (in Finnish). M.Sc. Thesis. Univ. Turku, \ 2002.\n[30] G. Pirillo and S. Varricchio. On uniformly repetitive \ semigroups. Semigroup Forum, 49:125", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "129. Springer-Verlag, New York, 1994.\n[31]", StyleBox[" ", FontWeight->"Bold"], "P.A.B. Pleasants. Non-repetitive sequences, Proc. Cambridge Phil. Soc., \ 68:267", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "274, 1970.\n[32]", StyleBox[" ", FontWeight->"Bold"], "G. Rozenberg and A. Salomaa. The Mathematical Theory of L-systems. \ Academic Press, New York, London, Toronto, Sydney, San Fransisco, 1980.\n\ [33]", StyleBox[" ", FontWeight->"Bold"], "A. Salomaa. Jewels of Formal Language Theory. Computer Science Press, \ Rockville, Maryland, 1981.\n[34] A. Thue. \[CapitalUDoubleDot]ber unendliche \ Zeichenreihe. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7:1", Cell[BoxData[ \(TraditionalForm\`\[Dash]\)]], "22, 1906.\n[35] S. Wolfram. A New Kind of Science. Wolfram Media, 2002." }], "Text"] }, FrontEndVersion->"4.2 for Microsoft Windows", ScreenRectangle->{{0, 1024}, {0, 695}}, AutoGeneratedPackage->None, ScreenStyleEnvironment->"Working", WindowToolbars->{"RulerBar", "EditBar"}, CellGrouping->Manual, WindowSize->{1013, 674}, WindowMargins->{{-1, Automatic}, {Automatic, 0}}, PrintingCopies->1, PrintingPageRange->{Automatic, Automatic}, CellLabelAutoDelete->True, Magnification->1.5, StyleDefinitions -> "ArticleClassic.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "Start"->{ Cell[66598, 2455, 1116, 34, 364, "Input", CellTags->"Start"], Cell[67876, 2496, 670, 27, 65, "Input", CellTags->"Start"], Cell[68549, 2525, 560, 22, 65, "Input", CellTags->"Start"], Cell[69335, 2558, 9203, 248, 947, "Input", CellTags->"Start"]} } *) (*CellTagsIndex CellTagsIndex->{ {"Start", 167512, 5918} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 132, 5, 99, "Subtitle"], Cell[1889, 58, 286, 9, 159, "Text"], Cell[2178, 69, 5337, 153, 615, "Text"], Cell[7518, 224, 17339, 528, 1719, "Text"], Cell[24860, 754, 31605, 1312, 1627, "Text"], Cell[56468, 2068, 113, 2, 63, "Text"], Cell[56584, 2072, 341, 10, 63, "Text"], Cell[56928, 2084, 785, 33, 63, "Text"], Cell[57716, 2119, 182, 3, 69, "Input"], Cell[57901, 2124, 71, 1, 43, "Input"], Cell[57975, 2127, 654, 18, 125, "Output"], Cell[58632, 2147, 850, 42, 63, "Text"], Cell[59485, 2191, 158, 2, 43, "Input"], Cell[59646, 2195, 71, 1, 43, "Input"], Cell[59720, 2198, 693, 18, 125, "Output"], Cell[60416, 2218, 451, 20, 39, "Text"], Cell[60870, 2240, 754, 38, 39, "Text"], Cell[61627, 2280, 246, 7, 39, "Input"], Cell[61876, 2289, 168, 2, 43, "Input"], Cell[62047, 2293, 271, 5, 95, "Input"], Cell[62321, 2300, 36, 3, 63, "Text"], Cell[62360, 2305, 81, 1, 43, "Input"], Cell[62444, 2308, 225, 8, 39, "Text"], Cell[62672, 2318, 69, 1, 43, "Input"], Cell[62744, 2321, 77, 1, 42, "Output"], Cell[62824, 2324, 161, 6, 39, "Text"], Cell[62988, 2332, 3431, 114, 279, "Text"], Cell[66422, 2448, 173, 5, 32, "Subtitle"], Cell[66598, 2455, 1116, 34, 364, "Input", CellTags->"Start"], Cell[67717, 2491, 156, 3, 32, "Subtitle"], Cell[67876, 2496, 670, 27, 65, "Input", CellTags->"Start"], Cell[68549, 2525, 560, 22, 65, "Input", CellTags->"Start"], Cell[69112, 2549, 220, 7, 32, "Subtitle"], Cell[69335, 2558, 9203, 248, 947, "Input", CellTags->"Start"], Cell[78541, 2808, 108, 1, 39, "Text"], Cell[78652, 2811, 7005, 230, 642, "Text"], Cell[85660, 3043, 322, 11, 39, "Text"], Cell[85985, 3056, 10589, 428, 614, "Text"], Cell[96577, 3486, 6084, 267, 330, "Text"], Cell[102664, 3755, 2898, 93, 192, "Text"], Cell[105565, 3850, 1930, 77, 136, "Text"], Cell[107498, 3929, 15915, 548, 866, "Text"], Cell[123416, 4479, 503, 11, 199, "Input"], Cell[123922, 4492, 2732, 96, 327, "Text"], Cell[126657, 4590, 27337, 984, 1079, "Text"], Cell[153997, 5576, 1022, 31, 183, "Text"], Cell[155022, 5609, 1581, 37, 255, "Text"], Cell[156606, 5648, 237, 5, 95, "Input"], Cell[156846, 5655, 350, 7, 111, "Text"], Cell[157199, 5664, 1139, 17, 279, "Text"], Cell[158341, 5683, 8300, 209, 1359, "Text"] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)