Steve Whealton








String Rewriting and the Fibonacci Word

Something that my musical and my visual work have in common is maintaining a proper balance between sameness and randomness. I am forever looking for new, interesting, and different ways to create patterns, to alter patterns, to merge patterns, and to render and manifest patterns in ways audible and visible.

String rewriting provides fertile ground for such pattern play. I came to it through fractals and then through L Systems. I had already spent a healthy portion of several years' doodling time developing my Greep Theory. The Thue-Morse Word and the Fibonacci Word seemed to have been invented just for me.

As with greeps, an alphabet is chosen and is usually limited to the first few letters of the lower-case Roman Alphabet. Both the Thue-Morse Word and the Fibonacci Word, for example, make do with nothing more than the set, {a, b}.

Unlike with greeps, however, the strings dealt with in rewriting are of varying, indefinite, or even of a theoretically infinite length. A given set of rules are applied over and over so as to produce, in theory at least, a string that can go on forever! This "infinite" string goes by the provocative name, the "Omega Word."

String rewriting has been studied for about a century, since the Norwegian logician and mathematician Axel Thue devised and perused "The Word Problem" as an exercise in logic.

Decades later, when computers began to arrive, Thue's pioneering constructs and notions were rediscovered. Computers, as it turned out, were very efficient at rewriting, and rewriting was basic to their nature.

Today, a field of study, called "Combinatorics on Words," has grown up from this beginning. It flourishes in France and elsewhere.

Whatever the originators' motives were in creating and pursuing string rewriting, their ideas lend themselves beautifully to the creation of interesting patterns. Because these strings typically have a fixed beginning point and proceed without limit from there, a kinship to music also suggests itself.

But my earliest work with strings was visual. Here is how it fell out.

 

The Thue-Morse Word

First, or earliest, things first: The abstract pattern that got string-rewriting off the ground around a hundred years ago was simple in the extreme. It was limited to an alphabet of but two letters, represented by "a" and "b," and consisted of one seed and two rules for production.

a

-

ab

a:

b

-

ba

 

The "a:" at the end of the first row tells you what to begin withóyou begin with the letter, "a." The two rules tell how to take it from there. "a - ab" means to search through the word at hand, and wherever you find an "a," replace it with an "ab." This process is the "rewriting" that gives the procedure its name. "b - ba," similarly, means to search through the word at hand, and wherever you find a "b," replace it with a "ba."

The first step, of course, is to start with the letter, "a." The letter, "a," becomes the first stage of the whole process. It can be thought of not only as a letter but also as a word.

The next step is to use the two rules as you look through the word at hand. Wherever you encounter (read) an "a," you counter with (write) an "ab." Perusing the first word, we read in the "a," and we write (in another place, as it were) an "ab." That "a" was the whole of the first word, so this stage is over.

At the next stage, the word to be examined consists of "ab." We peruse the word at hand, and rewrite everything we find there, according to the rules that have been provided.

The first letter we find in the word we are reading from is again an "a." We turn to the new word tha we are writing to and write "ab." Back on the read-in side, we encounter a "b." So back on the writing side after the "ab" that's already there, we now write "ba." This completes this phase and produces a new word, "abba."

This rewriting step can be repeated an indefinite number of times, at least in theory. The usefulness of the idea of an "Omega Word" lies mostly in the fact that certain tendencies begin to appear in the overall patterns as they grow ever larger. To appreciate this, let us carry out the Thue-Morse Word for several more steps:

a

                             

a

b

                           

a

b

b

a

                       

a

b

b

a

b

a

a

b

               

a

b

b

a

b

a

a

b

b

a

a

b

a

b

b

a

At each stage, the length of the Thue-Morse Word doubles. As a pattern, it would appear at first blush to be of only middling interest. For the principles by which it grows and flows are too simple to manifest themselves in an intriguing manner either visually or musically. Think of a tune made only of "A's" and "B's" strung out in one of the patterns shown above. Talk about minimalism!

But those raw sequences of "a's" and "b's" that double in length at every stage are only the beginning. Much of the usefulness of string rewriting comes from derived patterns, rather than from the raw ones.

The most famous pattern derived from the Thue-Morse Word involves counting. Consider adjacent "a's." The first two adjacent "a's" have two "b's" between them (abba). So we record the "2." The next two adjacent "a's" have a single "b" between them (aba), so we record a "1." So far, our derived pattern consists of "21."

Continuing, we find two "a's" with no "b" between them at all (aa). For this case, we record a "0." Continuing in this manner, we have a derived pattern of considerably more interest for visual or musical exploitation than is the raw Thue-Morse Word itself:

2 1 0 2 0 1 2 . . . .

It can be shown that this particular derived pattern "never repeats itself" in a precise way that logicians and theorists have defined and which gives them great pleasure. Theoretical results of this kind provide the reason why people like Axel Thue invent systems like string rewriting and The Word Problem in the first place.

 

The Fibonacci Word

For me, is has been an even simpler (How could anything be simpler than the Thue-Morse Word and not be trivial or redundant?) combination of rules and seed that has proven to be even more fruitful and suggestive than the Thue Morse Word has been. This is the Fibonacci Word, also called the Golden String.

a

-

ab

a:

b

-

a

 

This differs from the Thue-Morse Word solely in the rule for the letter, "b." It is, in fact, even simpler here than was the comparable rule for the letter, "b," in the Thue-Morse Word.

Here are the first few iterations:

a

                       

a

b

                     

a

b

a

                   

a

b

a

a

b

               

a

b

a

a

b

a

b

a

         

a

b

a

a

b

a

b

a

a

b

a

a

b

A close look at the first six iterations of the Fibonacci Word shows why "Fibonacci" was dragged into the naming of this pattern. The length of the six words and the number of "a's" and "b's" in each is as follows:

Word

Length

# of "a's"

# of "b's"

a

1

1

 

ab

2

1

1

aba

3

2

1

abaab

5

3

2

abaababa

8

5

3

abaababaabaab

13

8

5

All of the numbers above are Fibonacci Numbers, and their pattern is the familiar Fibonacci pattern of growth.

Let us now look over the Fibonacci Word (FW) more closely. We have worked it out only to the length of 13 total letters, but already certain things can be observed and in a few cases proven, in an informal and non-rigorous manner.

 

No "bb"?

First, we see that while there are many instances of "aa" in the FW, no "bb" appears at all. Can we expect that a "bb" may appear later on, as we continue churning out ever longer iterations of the FW? The answer is no, and it is fairly easy to see why.

What causes a "b" appear in the FW, in the first place? Looking at the rules, we notice that a "b" can occur only as part of an "ab" that derives from an "a" in the immediately previous iteration of the FW. Already, it is clear why no two "b's" can ever appear together. The first of such a pair is possible enough, as the second letter in an "ab" pair. But there is no way that a second "b" can ever follow immediately after the first one, for the only way that a "b" can occur at all is as the second letter in an "ab" pair.

 

No "aaa," either?

Notice also that no three "a's" appear in the thirteen-letter stage of the FW that we worked out, above. Again, it turns out that "aaa" is as impossible as is "bb" in the FW, but this time the logic of proof is more involved.

How could three "a's" in a row come to pass, given the rules? One way, of course, would be as the outcome of three "b's" in a row in the previous iteration. But even two "b's" cannot occur in a row, so that method of generating "aaa" has to be eliminated.

Another possibility might be as the result of that pattern, "bba" in the previous iteration. That would give "aaab," which would include the desired "aaa" pattern. But even two "b's" in a row cannot occur, so this, too, is out.

So what are all of the ways in which an "a" can appear? It can appear only as the result of a "b" in the previous iteration or as the first half of the "ab" that appears as the result of an "a" in the iteration two stages past. Two "a's" in a row are no help at all, for they give the "abab" pattern that doesn't produce even one pair of "a's." Clearly, there is no hope.

The above argument is not rigorous, but it gives an idea of how certain statements can be proved about these patterns, even in their Omega Word form.

The FW has many other fascinating properties. One is that no matter how far one calculates it, it never becomes completely repetitive, as "aabaabaabaabaabaabÖ" does, or even as "aababaababaababaababaababÖ.." does. This non-repetitiveness it shares with the Thue-Morse Word.

 

Palindrome

Another feature of the Fibonacci Word is less immediate. Lop off the final two letters at any stage, and what remains is a palindrome, reading the same forward as backward. The proof of this easily observable fact is well beyond me.

 

Sub-Words of the Fibonacci Word

The other features of the FW that most fascinate me and turn out in the end to be the most useful have to do with sub-words. A "sub-word" of the FW is any fragment such as the "abab" or the "baa" that were being discussed above. Certain patterns occur as observable sub-words of the FW "a," "b," "aa," "ab," "ba," etc., and certain conceivable patterns do not; for example, "bb," and "aaa," as already discussed.

Let us examine briefly some of the fragments that do and do not appear. At length one, two fragments are theoretically possible, "a," and "b." Both of them actually occur. At length two, the theoretically possibilities are "aa," "ab," "ba," and "bb." Here, the last one is never present, as we have seen. At length three, only four of the eight possible patterns occur. They are "aab," "aba," "baa," and "bab." This means that another four are never seen. They are "aaa," "abb," "bba," and "bbb." In this case, we can see why each of the three are no-shows. "aaa" was discussed specifically, and the other three contain the equally no-show pattern, "bb."

At length four, only five of the sixteen possible patterns actually occur. At length five, only six out of the thirty-two theoretically possible patterns are seen. In fact, whatever the length of sub-word that is examined, it is always found that the number of distinct sub-words actually occurring of that length in the FW is always one more than the length itself.

 

Which one Bears Two Children?

The final property of the FW involves yet another kind of parenthood. The more obvious kind of parenthood of one pattern over another is the simple act of one pattern generating another, as "abaab" generates "abaab" or even as sub-word "bab" generates "aaba." But consider another way of thinking of parenthood in this context. Think not of the sequences of patterns from one iteration to another, but rather of the sets of "legal" sub-words of each size.

A rigorous and mathematically completist theoretical point of view begins by observing that at length zero, there is but a single constituent sub-word, the sub-word of no size at all. Such a train of thought is perhaps frustrating or silly to most of us, but for a theorist it provides a satisfying underpinning for the remainder of the argument.

At length 1, two legal sub-words are found, "a" and "b." At length 2, three legal sub-words are found, "aa," "ab," and "ba." Here is where the new notion of parenthood comes in. One can think of "aa" and "ab" as children of parent "a" because both "aa" and "ab" can be created by appending a letter after the pattern, "a" By the same logic, pattern "ba" has parent pattern, "b."

Continuing, one sees that "aa" is parent of "aab," that "ab" is parent of "aba," and that "ba" is parent of both "baa" and "bab."

Simple arithmetic suggests that all but one of the sub-words of any given length will act as parent for a single sub-word of length one letter larger, while one sub-word alone will give birth to two progeny. No other pattern is possible, for all sub-words must have at least one child.

Moving from length three to length four, we note that "aab" produces "aaba," that "aba" gives rise to "abaa," as well as to "abab, and that "baa" sires "baab," At the next level, "aaba" produces "aabaa" and "aabab," "abaa" gives "abaab," "abab" gives "ababa," and "baab" gives "baaba," and "baba" gives "babaa."

Finally, let us collect together all of the sub-words so far that have turned out to have two, rather than one, progeny:

a, ba, aba, aaba,

Is this enough so that a pattern can be observed, or at least guessed at? Can one predict the sub-word of length five that will give rise to two progeny sub-words of length six?

It turns out that the hyperparental sub-word, at any given length, is precisely the FW itself of that length, written in reverse order.

There are many other features of the FW that are more subtle and more difficult to grasp, to prove, or to use.

 

A Few Home-Made Words

As is so often the case, the real world of theoreticians built upon the foundations provided by the Thue-Morse Word and by the Fibonacci Word and went their merry ways. For me and for my pictures and music, a divergent path is necessary. What I have done next is to create my own patterns of string rewriting, making up my own rules as I go along. In addition, I have created a few rudimentary methods of turning long strings into visual or musical patterns.

Keeping the two rules and altering only the seed, one can create a "Lucas Word" as follows:

a

-

ab

abb:

b

-

a

 

This differs from the Fibonacci Word solely in the seed. Here are the first few iterations:

a

b

b

                   

a

b

a

a

                 

a

b

a

a

b

a

b

           

a

b

a

a

b

a

b

a

a

b

a

   

This "Lucas Word" bears a strong resemblance to the original "Fibonacci Word." Only the lengths of each iteration provide an immediate sign of the difference.

 

On Beyond b

Next are two homespun words, each with its own rules and seed:

The first one expands the alphabet from {a, b} to {a, b, c} and the number of rules (counting "a:" as a rule of its own), necessarily, from three to four:

a

-

ab

a:

b

-

c

 

c

-

ba

 

Here are the first few iterations:

a

                       

a

b

                     

a

b

c

                   

a

b

c

b

a

               

a

b

c

b

a

c

a

b

         

a

b

c

b

a

c

a

b

b

a

a

b

c

All in all, this has proved to be my favorite "word." We will refer to it as "MFW." Even raw, the pattern shows promise. When derived patterns are created, the results are very much to my taste. That middle-ground between boredom and random has been achieved.

Here is another of my favorites. Again, a letter has been added bringing the alphabet to {a, b, c, d}, and again, a rule has been added:

a

-

ab

a:

b

-

d

 

c

-

a

 

d

-

dc

 

Here are the first few iterations:

a

                       

a

b

                     

a

b

d

                   

a

b

d

d

c

               

a

b

d

d

c

d

c

a

         

a

b

d

d

c

d

c

a

d

c

a

a

b

Notice how "abddc" and "dcaab" seem somehow to complement one another. With four distinct letters as elements, even the raw pattern has direct musical interest.

Finally, patterns can be derived from sub-words more or less directly. The first step is to list all of the "legal" sub-words of some given size, and the next steps involve associating each sub-word with a color, a pitch, or some other component quality of the image or the music that is being created.

 

Analyzing the MFW

Let us focus on my favorite word, beginning with a list of its sub-words of lengths two and three:

Here are the rules and seed once more:

a

-

ab

a:

b

-

c

 

c

-

ba

 

And here again are the first few iterations:

a

                       

a

b

                     

a

b

c

                   

a

b

c

b

a

               

a

b

c

b

a

c

a

b

         

a

b

c

b

a

c

a

b

b

a

a

b

c

Before beginning our analysis, let us carry the rewriting procedure out by one more stage. Here is that new bottom line:

a b c b a c a b b a a b c c a b a b c b a

The laws of combinatorics mandates 9 possible permutations of two letters over the alphabet, {a, b, c}. These are:

aa

ba

ca

ab

bb

cb

ac

bc

cc

Returning to the first 21 letters of MFW, we find that all 9 of the two-letter permutations shown above appear at least once in the 21. In the order in which they appear, here are the 20 adjacent pairs that make up the first 21 letters of MFW:

ab

bc

cb

ba

ac

ca

ab

bb

ba

aa

ab

bc

cc

ca

ab

ba

ab

bc

cb

ba

Each pair is shown in bold the first time it occurs.

The next question is this: "How do you go from pairs of letters to colors or to pitches?" Clearly, the way is to line up the colors or the pitches in some desired order, and then to associate the two-letter patterns with them, one by one.

Pitches can usually be thought of as being in some sort of convenient order in the first place. Whether one is focusing on all 12 pitches classes in the familiar well-tempered scale or whether one has created some other set of tones or of pitch classes, it is both usual and natural to read from the lowest pitch up to the highest.

Colors may not carry such an obvious ordering as do pitches. But the computer and its software, at least, has designated the colors that it can use with a simple set of color index numbers. This alone puts the colors into a convenient order. If the computer's color palette is too arbitrary for your taste, you can create your own, with all of the meaningful sequential orderliness you desire.

 

Making the Associations

Whatever one will be associating the two-letter patterns with, the question still remains how best to do it. One way is to take the patterns in the order in which they appear. That would mean taking the list, repeated just below, of 20 adjacent pairs, and reading from that list the 9 patterns in bold face from left to right.

ab

bc

cb

ba

ac

ca

ab

bb

ba

aa

ab

bc

cc

ca

ab

ba

ab

bc

cb

ba

Those 20 patterns, in the order shown above, can now be associated with an ordered list of colors or of pitches (or of whatever else is desired). Simply take the 9 patterns in bold, reading from left to right, and match them to the list of pitches, colors, or whatever.

This would create a chart rather like the one shown below:

ab

bc

cb

ba

ac

ca

bb

aa

cc

1

2

3

4

5

6

7

8

9

From this point on, the nine needed associations are set, and the task of rendering the rewritten word in visible or musical form can proceed.

 

Using Alphabetical Order with Pitches

When patterns are linked to pitches, however, a problem arises. Presuming that the pitches are ordered from the ground up, then the melody that results from associating patterns and pitches by taking the patterns in the order in which they occur will create a melody that starts out as a scale, going upward.

Therefore, when I'm matching my letter-pair patterns up with pitches, my usual method is use alphabetical order rather than the order in which the pairs occur within the Omega Word. This would associate "aa" with the lowest of the nine pitches in whatever scale I chose, and "cc" with the highest. Playing the first handful of letters from some Omega Word sequence rendered into pitches will now be far more interesting and characteristic than would a simple rising scale would be.

If we use alphabetical order to associate the 9 possible pairs with a simple musical scale, then we can look at the original set of 20 actually occurring pairs, and see what kind of tune we can make it into.

The first step is to arrange the 9 pairs in alphabetical order, and then to choose 9 pitches to go with them. We will begin at Middle C and go upward in C major.

aa

ab

ac

ba

bb

bc

ca

cb

cc

C

D

E

F

G

A

B

C

D

Using these matchups, here is how the 20 pairs can be made into 20 notes of a melody:

ab

bc

cb

ba

ac

ca

ab

bb

ba

aa

ab

bc

cc

ca

ab

ba

ab

bc

cb

ba

D

B

C'

F

E

B

D

G

F

C

D

B

D'

B

D

F

D

B

C'

F

In this description, C' and D' are an octave higher than are C and D, respectively.

One can consider sub-words of length four, five, or larger. The overall technique is the same.

 

Future Plans

One thing I like to do is to create musical patterns not just from one iteration (row) of the MFW or of some other pattern, but using several rows, all at once. The lowest row might govern durations, while other rows would control pitch, loudness, orchestration, etc. Getting a good result from this idea requires musical, as well as mathematical, thinking.

On the visual side, a long string of numbers may be a wonderful thing, but it does not a picture make. In order to achieve a two-dimensional pattern, something more is needed.

I like to use one-dimensional Cellular Automata, deriving each row of index numbers (and hence also of colored pixels) from the row of numbers just above it. But that is a topic for another day.

 








Internal Links:

washingtonart.net

HOME

TALK

LINKS

IMAGES

PÆAN

TECH

PHOTO

MATH

Programming

Algebra

Sequences

Goo

Turtle

Patterns

Squeeze

Ternary

Bio

Raster

FPOI

Disguise

Number Wars

Glass

Fibword

Gray

Geometry

Paint

Banding

GBT

greep

Misc

pfcpn