Dab solver - Combinatorics on words

Most tools require the use of JavaScript. If you are using Firefox with the NoScript addon, please mark toolserver.org as trusted. See the Help page for details.

Feedback / Report a bug

1 point on this page / 19,509 points earned collectively this month / Disambiguate pages on your watchlist

Other contributors to the study of unavoidable patterns include [[van der Waerden]].  His theorem states that if the positive integers are partitioned into k classes, then there exists a class c such that c contains an arithmetic progression of some unknown length.  An [[arithmetic progression]] is a sequence of numbers in which the difference between adjacent numbers remains constant.^ref 

When examining unavoidable patterns [[sesquipower]]s are also studied.  For some patterns x,y,z, a sesquipower is of the form x, xyx, xyxzxyx, .... This is another pattern such as square-free, or unavoidable patterns.  Coudrain and [[Schützenberger]] mainly studied these sesquipowers for [[group theory]] applications.  In addition,  proved that sesquipowers are all unavoidable.  Whether the entire pattern shows up, or only some piece of the sesquipower shows up repetitively, it is not possible to avoid it.^ref

Single scrollbar

[[Combinatorics]] on words is a fairly new field of [[mathematics]], branching from [[combinatorics]], which focuses on the study of [[word (group theory)|words]] and [[formal language]]s.  The subject looks at letters or [[symbol]]s, and the [[sequence]]s they form.  '''Combinatorics on words''' affects various areas of mathematical study, including [[algebra]] and [[computer science]].  There have been a wide range of contributions to the field.  Some of the first work was on [[square-free word]]s by Thue in the early 1900s.  He and colleagues observed patterns within words and tried to explain them.  As time went on, combinatorics on words became useful in the study of [[algorithm]]s and [[Computer programming|coding]].  It led to developments in [[abstract algebra]] and answering open questions.

==Definition==
Combinatorics is an area of [[discrete mathematics]]. Discrete mathematics is the study of countable structures. These objects have a definite beginning and end. The study of enumerable objects is the opposite of disciplines such as [[mathematical analysis|analysis]], where [[calculus]] and [[infinite set|infinite]] structures are studied. Combinatorics studies how to count these objects using various representation. Combinatorics on words is a recent development in this field, which focuses on the study of words and formal languages. A formal language is any set of symbols and combinations of symbols that people use to communicate information.<ref name=Origins />

Some terminology relevant to the study of words should first be explained. First and foremost, a word is basically a sequence of symbols, or letters, in a [[finite set]].<ref name=Origins>{{cite journal|last=Berstel|first=Jean|coauthors=Dominique Perrin|title=The origins of combinatorics on words|journal=European Journal of Combinatorics|year=2007|month=April|volume=28|issue=3|pages=996–1022|url=http://www.sciencedirect.com.libproxy.clemson.edu/science/article/pii/S0195669805001629|accessdate=February 14, 2013}}</ref> One of these sets is known by the general public as the [[alphabet]]. 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. The alphabet is a [[set (mathematics)|set]], so as one would expect, the [[empty set]] is a [[subset]]. In other words, there exists a [[unique]] word of length zero. The length of the word is defined by the number of symbols that make up the sequence, and is denoted by |w|.<ref name=Origins /> Again looking at the example "encyclopedia", |w| = 12, since encyclopedia has twelve letters. Most people have a knowledge of [[factorization|factoring]] large numbers into their decomposition. This idea can be applied to words as well. A factor of a word is a block of consecutive symbols.<ref name=Origins /> Using a different example: if the word "summer" is examined, it has the factor "m", since the letter is repeated twice.

In addition to examining sequences in themselves, another area to consider of combinatorics on words is how they can be represented visually. In mathematics various structures are used to encode data. A common structure used in combinatorics is referred to as a [[tree structure]]. A tree structure is a [[graph (mathematics)|graph]] where the [[vertex (graph theory)|vertices]] are connected by one line, called a path or [[Glossary of graph theory#Basics|edge]]. These trees may or may not contain [[cycle (graph theory)|cycles]], and may or may not be complete. It is possible to [[Character encoding|encode]] a word, since a word is constructed by symbols, and encode the data by using a tree.<ref name=Origins /> This gives a visual representation of the object.

==Major contributions==
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]]. Their first book was published in 1983, when combinatorics on words became more widespread.<ref name=Origins />

==Patterns==

===Patterns within words===
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 word]]s. Square-free words do not have adjacent factors.<ref name=Origins /> To clarify, "summer" is not square-free since m is repeated consecutively, while "encyclopedia" is square-free. Thue proves his conjecture on the existence of infinite square-free words by using [[string substitution|substitution]]s. A substitution is a way to take a symbol and replace it with a word. He uses this technique to describe his other contribution, the [[Thue-Morse sequence]], or Thue-Morse word.<ref name=Origins />

Thue wrote two papers on square-free words, the second of which was on the Thue-Morse word. [[Marston Morse]] is included in the name because he discovered the same result as Thue did, yet they worked independently. Thue also proved the existence of an overlap-free word. An overlap-free word is when, for two symbols x and y, the pattern xyxyx does not exist within the word. He continues in his second paper to prove a relationship between infinite overlap-free words and square-free words. He takes overlap-free words that are created using two different letters, and demonstrates how they can be transformed into square-free words of three letters using substitution. Eugène Prouhet continued with Thue's work to improve the Thue-Morse word.<ref name=Origins />

As was previously described, words are studied by examining the sequences made by the symbols. Patterns are found, and they are able to be described mathematically. Patterns can be either avoidable patterns, or unavoidable. A significant contributor to the work of [[unavoidable pattern]]s, or regularities, was [[Frank P. Ramsey|Frank Ramsey]] in 1930. His important theorem states that for integers k, m≥2, there exists a least positive integer R(k,m) such that despite how a complete graph is colored with two colors, there will always exist a solid color subgraph of each color.<ref name=Origins />

Other contributors to the study of unavoidable patterns include [[van der Waerden]]. His theorem states that if the positive integers are partitioned into k classes, then there exists a class c such that c contains an arithmetic progression of some unknown length. An [[arithmetic progression]] is a sequence of numbers in which the difference between adjacent numbers remains constant.<ref name=Origins />

When examining unavoidable patterns [[sesquipower]]s are also studied. For some patterns x,y,z, a sesquipower is of the form x, xyx, xyxzxyx, .... This is another pattern such as square-free, or unavoidable patterns. Coudrain and [[Schützenberger]] mainly studied these sesquipowers for [[group theory]] applications. In addition, <<link:0>> proved that sesquipowers are all unavoidable. Whether the entire pattern shows up, or only some piece of the sesquipower shows up repetitively, it is not possible to avoid it.<ref name=Origins />

===Patterns within alphabets===
[[Necklace (combinatorics)|Necklaces]] are constructed from words of circular sequences. They are most frequently used in [[music]] and [[astronomy]]. Flye Sainte-Marie in 1894 proved there are 22n-1-n [[Binary number|binary]] [[de Bruijn]] necklaces of length 2n. A de Bruijn necklace contains factors made of words of length n over a certain number of letters. The words appear only once in the necklace.<ref name=Origins />

In 1874, [[Émile Baudot|Baudot]] developed the code that would eventually take the place of [[Morse code]] by applying the theory of binary de Bruijn necklaces. The problem continued from Sainte-Marie to [[M. H. Martin|Martin]] in 1934, who began looking at algorithms to make words of the de Bruijn structure. It was then worked on by [[K. Posthumus|Posthumus]] in 1943.<ref name=Origins />

==Language Hierarchy==
{{main|Chomsky hierarchy}}
Possibly the most applied result in combinatorics on words is the Chomsky hierarchy, developed by [[Noam Chomsky]]. He studied formal language in the 1950s.<ref name=Chomsky>{{cite journal|last=Jäger|first=Gerhard|coauthors=James Rogers|title=Formal language theory: refining the Chomsky hierarchy|journal=Philosophical Transactions of the Royal Society B|year=2012|month=July|volume=367|issue=1598|pages=1956–1970|accessdate=February 14, 2012}}</ref> His way of looking at language simplified the subject. He disregards the actual meaning of the word, does not consider certain factors such as frequency and context, and applies patterns of short terms to all length terms. The basic idea of Chomsky's work is to divide language into four levels, or the language [[hierarchy]]. The four levels are: [[Regular language|regular]], [[Context-free language|context-free]], [[Context-sensitive language|context-sensitive]], and [[Recursively enumerable language|computably enumerable]] or unrestricted.<ref name=Chomsky /> Regular is the least complex while computably enumerable is the most complex. While his work grew out of combinatorics on words, it drastically affected other disciplines, especially [[computer science]].<ref name="Word Avoiding">{{cite journal|last=Morales-Bueno|first=Rafael|coauthors=Baena-Garcia, Carmona-Cejudo, Castillo|title=Counting Word Avoiding Factors|journal=Electronic Journal of Mathematics and Technology|year=2010|issue=4.3|pages=251|accessdate=February 10, 2013}}</ref>

==Word Types==

===Sturmian Words===
{{main|Sturmian word}}
[[Sturmian word]]s, created by François Sturm, have roots in combinatorics on words. Consider a word containing factors of length n. In a Sturmian word, the factor of length n appears exactly n+1 times.<ref name=Origins />

===Lyndon Word===
{{main|Lyndon word}}
A [[Lyndon word]] is a word over a given alphabet that is written in its simplest and most ordered form out of its respective [[conjugacy class]]. Lyndon words are important because for any given Lyndon word x, there exists Lyndon words y and z, with y<z, x=yz. Further, there exists a [[Chen–Fox–Lyndon theorem|theorem by Chen, Fox, and Lyndon]], that states any Lyndon word has a unique factorization of Lyndon words, where the factorization words are [[non-increasing]]. Due to this property, Lyndon words are used to study [[algebra]], specifically [[group theory]]. They form the basis for the idea of [[commutators]].<ref name=Origins />

==Visual Representation==
[[Alan Cobham (mathematician)|Cobham]] contributed work relating Prouhet's work with [[finite automata]]. A mathematical graph is made of edges and [[node (graph theory)|node]]s. With finite automata, the edges are labeled with a letter in an alphabet. To use the graph, one starts at a node and travels along the edges to reach a final node. The path taken along the graph forms the word. It is a finite graph because there are a countable number of nodes and edges, and only one path connects two [[distinct]] nodes.<ref name=Origins />

[[Gauss code]]s, created by [[Carl Friedrich Gauss]] in 1838, are developed from graphs. Specifically, a [[closed curve]] on a [[plane (geometry)|plane]] is needed. 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]].<ref name=Origins />

==Group Theory==
[[Walther Franz Anton von Dyck]] began the work of combinatorics on words in group theory by his published work in 1882 and 1883. He began by using words as group elements. [[Lagrange]] also contributed in 1771 with his work on [[permutation groups]].<ref name=Origins />

One aspect of combinatorics on words studied in group theory is reduced words. A group is constructed with words on some alphabet including [[Generator (Mathematics)|generator]]s and [[inverse element]]s, excluding factors that appear of the form aā or āa, for some a in the alphabet. [[Reduced words]] are formed when the factors aā, āa are used to cancel out elements until a [[unique]] word is reached.<ref name=Origins /> 
 
[[Nielsen transformation]]s were also developed. For a set of elements of a [[free group]], a Nielsen transformation is achieved by three transformations; replacing an element with its inverse, replacing an element with the [[product (mathematics)|product]] of itself and another element, and eliminating any element equal to 1. By applying these transformations Nielsen reduced sets are formed. A reduced set means no element can be multiplied by other elements to cancel out completely. There are also connections with Nielsen transformations with Sturmian words.<ref name=Origins />

===Considered problems===
One problem considered in the study of combinatorics on words in group theory is the following: for two elements x,y of a [[semigroup]], does x=y [[modular arithmetic|modulo]] the defining [[relation (mathematics)|relation]]s of x and y. [[Emil Leon Post|Post]] and [[Andrey Markov, Jr.|Markov]] studied this problem and determined it [[undecidable problem|undecidable]]. Undecidable means the theory cannot be proved.<ref name=Origins />

The [[William Burnside|Burnside]] question was proved using the existence of an infinite cube-free word. This question asks if a group is finite if the group has a definite number of generators and meets the criteria xn=1, for x in the group.<ref name=Origins />

Many word problems are undecidable based on the [[Post correspondence problem]]. The Post correspondence problem states for substitutions x, and y [[Map (mathematics)|mapping]] from some alphabet A to some alphabet B, does there exist a word m in A such that x(m)=y(m)? Post determined that this problem is undecidable, thus when word problems are reduced to this basic problem, they can be determined as well to be undecidable.<ref name=Origins />

==Other applications==
Combinatorics on words have applications on [[equations]]. Makanin proved that it is possible to find a solution for a finite system of equations, when the equations are constructed from words.<ref name=Origins />

==See also==
*[[Fibonacci word]]
*[[Kolakoski sequence]]
*[[Partial word]]
*[[Shift space]]
*[[Word metric]]
*[[Word problem (computability)]]
*[[Word problem (mathematics)]]
*[[Word problem for groups]]
*[[Young-Fibonacci lattice]]

==References==
{{reflist}}

==Further reading==
{{refbegin|33em}}
*[http://www-igm.univ-mlv.fr/%7Eberstel/Articles/2007Origins.pdf The origins of combinatorics on words], Jean Berstel, Dominique Perrin, European Journal of Combinatorics 28 (2007) 996–1022
*[http://www-igm.univ-mlv.fr/~berstel/Articles/2003TutorialCoWdec03.pdf Combinatorics on words - a tutorial], Jean Berstel and Juhani Karhumäki.  Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 79:178-228, 2003.
*[http://www.tucs.fi/publications/attachment.php?fname=TR645.pdf Combinatorics on Words: A New Challenging Topic], Juhani Karhumäki.
*{{cite book | chapter = Combinatorics of words | id = {{citeseerx|10.1.1.54.3135}} |first = Christian | last1 = Chorut | first2 =  Juhani | last2 = Karhumäki | title = Handbook of formal languages | volume = 1 | editor1-first = Grzegorz | editor1-last = Rozenberg | editor2-first =  Arto | editor2-last = Salomaa | publisher = Springer | year = 1997 | isbn = 978-3-540-60420-4 }}
*{{Citation | last1=Lothaire | first1=M. | authorlink = M. Lothaire | title=Combinatorics on words | url=http://books.google.com/books?id=UV9_3plEr8wC | publisher=Addison-Wesley Publishing Co., Reading, Mass. | series=Encyclopedia of Mathematics and its Applications | isbn=978-0-201-13516-9 | mr=675953 | zbl=0514.20045 | year=1983 | volume=17}}
*{{Citation | last1=Lothaire | first1=M. | authorlink = M. Lothaire | title=Algebraic combinatorics on words | url=http://www-igm.univ-mlv.fr/~berstel/Lothaire/AlgCWContents.html | publisher=[[Cambridge University Press]] | series=Encyclopedia of Mathematics and its Applications | isbn=978-0-521-81220-7 | mr=1905123 | zbl=1001.68093 | year=2002 | volume=90}}
*"Infinite words: automata, semigroups, logic and games", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 978-0-12-532111-2.
*{{Citation | last1=Lothaire | first1=M. | authorlink = M. Lothaire | title=Applied combinatorics on words | url=http://www-igm.univ-mlv.fr/~berstel/Lothaire/AppliedCW/AppCWContents.html | publisher=[[Cambridge University Press]] | series=Encyclopedia of Mathematics and its Applications | isbn=0-521-84802-4 | mr=2165687 | zbl=1133.68067 | year=2005 | volume=105}}
*"Algorithmic Combinatorics on Partial Words", Francine Blanchet-Sadri, CRC Press, 2008, ISBN 978-1-4200-6092-8.
* {{citation | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
*"Combinatorics of Compositions and Words", Silvia Heubach, Toufik Mansour, CRC Press, 2009, ISBN 978-1-4200-7267-9.
*"Word equations and related topics: 1st international workshop, IWWERT '90, Tübingen, Germany, October 1–3, 1990 : proceedings", Editor: Klaus Ulrich Schulz, Springer, 1992, ISBN 978-3-540-55124-9
*"Jewels of stringology: text algorithms", Maxime Crochemore, [[Wojciech Rytter]], World Scientific, 2003, ISBN 978-981-02-4897-0
* {{cite book | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 }}
*"Patterns in Permutations and Words", Sergey Kitaev, Springer, 2011, ISBN 9783642173325
*"Distribution Modulo One and Diophantine Approximation", Yann Bugeaud, Cambridge University Press, 2012, ISBN 9780521111690
{{refend}}

==External links==
*[http://www-igm.univ-mlv.fr/~berstel/ Jean Berstel's page]
*[http://users.utu.fi/harju/combwords.htm Tero Harju's page]
*[http://www.labri.fr/perso/melancon/Words/Publications/index.html Guy Melançon's page]

[[Category:Combinatorics on words]]

Edit summary:
This is a minor edit Watch this page

Cancel

Dab solver - Combinatorics on words

Tools

Interaction