Here you can find an interactive visualizer demonstrating how an algorithm works deciding whether a given word is a fixed point of a nontrivial morphism. (It replaces an older Java applet written by Vojtěch Matocha.)

The algorithm was published by Š. Holub here (see the paper for related references).

A more detailed complexity analysis (by Š. Holub and V. Matocha) is available here.

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Wale� showed that the algorithm can be modified to run in linear time.

The algorithm constructs a morphism fixing the input word with the minimal number of non-erased letters.

Any feedback or bug report is welcome. Please write to

Given a word w, we want to construct a stabilizer of w, that is, a morphism f satisfying f(w)=w. Such a stabilizer always trivially exists, namely the identity. We are therefore interested in the question whether there is a nontrivial morphism fixing w.

An important fact is that we can (and will) limit ourselves to idempotent stabilizers, that is, morphisms satisfying

for each non-erased letter X. An idempotent stabilizer maps each letter X to a word in which X occurs exactly once.

In addition, we would like to construct the "least trivial" morphism fixing w, namely the morphism with minimal possible support (the set of non-erased letters). It turns out that such a minimal stabilizer is "almost" unique.

The minimal stabilizer is ambivalent in two respects

• First, there may exist so called "twin" letters, which can generate each other and therefore the corresponding image has two (or more) possible supports. For a trivial example, consider the word
  ABACA,
  which is fixed both by
  B → ABACA
  and by
  C → ABACA.
  
  
• Second, given a support, there may remain a certain freedom in the way how the non-erased letters share the word. An example is the word
  BAADBAAECAADCAAE,
  where erased letters A can be produced either by B and C:
  B → BAA, C → CAA, D → D, E → E
  or by D and E:
  B → B, C → C, D → AAD, E → AAE
  or jointly by B,C,D and E:
  B → BA, C → CA, D → AD, E → AE.

The visualizer yields a graphical representation of the algorithm (the canvas in the center) and three textual outputs. The input word may consist of up to 60 alphanumeric characters; press Enter or the RUN button to start. The buttons below the input field insert the examples described on this page.

The three textual outputs are the following:

1. The Minimal Morphism panel (bottom left) shows the standard minimal stabilizer, which is defined by the following two rules, corresponding to the two above ambiguities:
   • the leftmost "twin" is used
   • left-expansion of a non-erased letter is preferred
   Erased letters are listed with the image ε (the empty word). The panel also displays a badge saying whether the word is (morphically) PRIMITIVE — the minimal stabilizer is the identity — or IMPRIMITIVE.
2. The All Morphisms panel (bottom right), an "advanced" one, gives a representation of all possible minimal stabilizers.
   For the first example above, the panel yields:
   B, C → ABACA
   showing that the word ABACA has two possible preimages.
   For the second above example the panel yields:
   B → BP₁     P₁ ≤ AA
   D → P₁^-1AAD
   E → P₁^-1AAE
   C → CP₁
   The condition P₁ ≤ AA says that the word P₁ is a prefix of AA. It can therefore have three different values:
   P₁=AA
   P₁ is empty
   P₁=A
   yielding the three possible minimal stabilizers above respectively.
   Note that the standard minimal stabilizer has P₁ empty.
   Below the parametric representation, the panel offers a button for each possible choice of the prefix values (for the example above: P₁=ε, P₁=A, P₁=AA). Clicking a button displays the corresponding concrete minimal stabilizer and updates the factorization shown in the graphics and in the FACT line of the log accordingly.
   To see a more complex example try the visualization with the word
   DHFFAGGBFFAGGBFFCGGEDHFFCGGBFFAGGBFFCGGE
3. The Algorithm Log (left sidebar) records the run of the algorithm. The log consists of pairs of lines, each of them corresponding to several graphical steps described below. Clicking a log line moves the graphics to the corresponding step.
   The log then gives so called morphic factorization of the input word, corresponding to the discovered standard minimal stabilizer. This is simply the factorization into images of letters from the support. This factorization is shown also graphically (the last step of the visualization), in the log it is given by the FACT line with the list of cuts (that is, positions delimiting images of support letters).

The algorithm works by detecting obligatory left and right positions; and obligatory expanding letters, that is, letters that have to be in the support (cannot be erased).
Positions are borders between two consecutive letters (including the first position 0 and the last position whose number is the length of the word). Numbers of positions are shown in the visualization.
The terms left and right position are relative to a given stabilizer and describe whether a given position lies to the left or to the right from the support letter by which it is "produced".
For example, in the stabilizer B → ABAA of the word ABAAABAA the positions 0,1,4,5 are left, and positions 2,3,4,6,7,8 are right. Note that the position 4 is both left and right due the fact that it is a cut (a border position between two images).

Another fundamental concept is the neighborhood of a letter. The neighborhood of a letter in the word w is the largest possible extension of the letter which is "compatible" with the word w, or, in other terms, the largest context of the letter in w. Clearly, the image of a letter by a stabilizer is limited by its neighborhood.

Obligatory left and right positions are now defined by the following rules for positions

1. The first position and the last position are both left and right.
2. The position just to the left of an expanding letter is a left position, and the position just to the right of an expanding letter is a right position.
3. Left border of a neighborhood of an expanding letter is a right position, and right border of a neighborhood of an expanding letter is a left position (yes, it is crosswise in this case).
4. Neighborhoods of different occurences of the same expanding letter are synchronized. That is, they have the same structure of left and right positions.

Obligatory left and right positions are marked in the visualization by blue dots (below the word) and green dots (above the word) respectively.

In order to define obligatory expanding letters, we need two more notions. A stretch factor is a factor between a left position and a right position. The weight of a letter is the number of its occurrences in w. We now have the following rules for expanding letters:

5. Each stretch factor contains an expanding letter. The letter within a stretch factor that has minimum weight must be expanding. (NB: The weight is the number of ocurrences in the whole word w, not just in the stretch factor in question!)
6. If more letters have the same minimum weight, then any of them can be chosen (standard choice is the leftmost one).

The algorithm, and likewise the visualization, proceeds in rounds consisting of following steps, which are recorded in the Algorithm Log and visualized graphically (the current step is named in the status box next to the navigation buttons):

• Find a stretch factor that does not contain any expanding letter (graphical step Stretch Factor, marked by a red bracket below the word). If there is no such stretch factor, the algorithm terminates.
• Add a new expanding letter according to rules 5 and 6 (graphical step New Exp. Char; the new expanding letter is circled in gold, previously added expanding letters in orange).

Previous two steps are recorded in the log by a line of the following form: which says:

• Find the neighborhood of the new expanding letter (graphical step Neighbourhood, marked by blue dashed brackets above the word, for all occurrences of the letter).

This is reported by a line like: which means:

• Mark left and right positions according to rules 2 and 3, and synchronize neighborhoods according to rule 4 (graphical step Default L & R, displaying the resulting left and right positions).

The graphical steps can be browsed using the FIRST/PREV/NEXT/LAST buttons below the canvas, or with the arrow keys.

Note that the algorithm starts by marking the first and the last position as both left and right (rule 1), whence the first stretch factor leading to the choice of the first expanding letter is always the whole word.

The above mentioned paper by Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Wale� essentially shows that not all steps described here are necessary in order to obtain the resulting factorization.