Repetition-Free Words
Abstract Diamond Implementation Diamond Paper
Blanchet-Sadri Abraham Elara

First applet: Given a full word w, a positive integer p, and a non-negative integer d, this implementation outputs a d-valid, p-periodic partial word contained in w if any such word exists. A d-valid partial word is one that has no two holes within distance d.

Second applet: Given a morphism and a seed string that determine a fixed point, together with a non-negative integer n, this implementation outputs the list of all length n factors of this fixed point.

Usage: Morphisms are inputted by specifying the alphabet (as a list with no delimiter) in the "alphabet" field and the images of these letters (as a space-delimited list in the corresponding order) in the "images" field. The morphism defined by a→bc, b→bd, c→ca, d→cb is provided as an example.

There are several restrictions on the morphism and seed: The morphism must be such that the image of each letter has length at least 2. Furthermore, the seed must be a prefix of its image. (This ensures that with repeated application of the morphism to the seed, the word grows exponentially and converges to a fixed point.)

Tip: If your morphism maps some letter to a word of length less than 2, try raising the morphism to a higher power, since this new morphism will generate the same fixed point. For example, consider the morphism defined by a→abc, b→ac, c→b. The square of this morphism is defined by a→abcacb, b→abcb, c→ac, which sends every letter to a word of length at least 2.

Valid XHTML 1.0!
Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0754154. The Department of Defense is also gratefully acknowledged.
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.
Partial Words Logo
Valid CSS!