Combinatorics on words

Combinatorics on words affects various areas of mathematical study, including algebra and computer science.

Some of the first work was on square-free words by Axel Thue in the early 1900s.

It led to developments in abstract algebra and answering open questions.

First and foremost, a word is basically a sequence of symbols, or letters, in a finite set.

For example, the word "encyclopedia" is a sequence of symbols in the English alphabet, a finite set of twenty-six letters.

Since a word can be described as a sequence, other basic mathematical descriptions can be applied.

is defined by the number of symbols that make up the sequence, and is denoted by

In addition to examining sequences in themselves, another area to consider of combinatorics on words is how they can be represented visually.

A tree structure is a graph where the vertices are connected by one line, called a path or edge.

The first books on combinatorics on words that summarize the origins of the subject were written by a group of mathematicians that collectively went by the name of M. Lothaire.

[1] A main contributor to the development of combinatorics on words was Axel Thue (1863–1922); he researched repetition.

Thue's main contribution was the proof of the existence of infinite square-free words.

Thue proves his conjecture on the existence of infinite square-free words by using substitutions.

Marston Morse is included in the name because he discovered the same result as Thue did, yet they worked independently.

[1] As was previously described, words are studied by examining the sequences made by the symbols.

A significant contributor to the work of unavoidable patterns, or regularities, was Frank Ramsey in 1930.

[1] Other contributors to the study of unavoidable patterns include van der Waerden.

Coudrain and Schützenberger mainly studied these sesquipowers for group theory applications.

A de Bruijn necklace contains factors made of words of length n over a certain number of letters.

The problem continued from Sainte-Marie to Martin in 1934, who began looking at algorithms to make words of the de Bruijn structure.

The four levels are: regular, context-free, context-sensitive, and computably enumerable or unrestricted.

While his work grew out of combinatorics on words, it drastically affected other disciplines, especially computer science.

Due to this property, Lyndon words are used to study algebra, specifically group theory.

With finite automata, the edges are labeled with a letter in an alphabet.

If the curve only crosses over itself a finite number of times, then one labels the intersections with a letter from the alphabet used.

Traveling along the curve, the word is determined by recording each letter as an intersection is passed.

Gauss noticed that the distance between when the same symbol shows up in a word is an even integer.

By applying these transformations Nielsen reduced sets are formed.

[1] One problem considered in the study of combinatorics on words in group theory is the following: for two elements

[1] The Burnside question was proved using the existence of an infinite cube-free word.