Combinatorics on words

Construction of a Thue-Morse infinite word

Combinatorics on words is a branch of mathematics which applies combinatorics to words and formal languages. The study of combinatorics on words arose independently within several branches of mathematics, e.g. number theory, group theory and probability. It has applications to combinatorial enumeration and fractal analysis and appears in problems of theoretical computer science, automata theory, symbolic dynamics and linguistics. While many applications are new, the classical Chomsky–Schützenberger hierarchy of classes of formal grammars is perhaps the best known result in the field. The development of computerized text and string processing has led to important applications of combinatorics on words. It is involved in the core algorithms for text processing, natural language processing, speech processing and bioinformatics.

The study of combinatorics of words goes back to the works of Axel Thue on nonrepetitive sequences of symbols at the beginning of the 20th century. In the years following there were a few researchers working on words, then major work began in the 1950s when Marcel-Paul Schützenberger studied words in his work on coding theory, and Pyotr Novikov and Sergei Adian studied words in connection with Burnside's problem for groups. The study of combinatorics on words really began to develop rapidly after the publication of Lothaire's book in 1983. Lothaire is a nom de plume of a group of researchers working in this area.

See also

• Fibonacci word
• Kolakoski sequence
• Lyndon word
• M. Lothaire
• Necklace (combinatorics)
• Partial word
• Shift space
• Squarefree word
• Sturmian word
• Thue-Morse sequence
• Word (group theory)
• Word metric
• Word problem (computability)
• Word problem (mathematics)
• Word problem for groups
• Young-Fibonacci lattice

References

• The origins of combinatorics on words, Jean Berstel, Dominique Perrin, European Journal of Combinatorics 28 (2007) 996–1022
• Combinatorics on words - a tutorial, Jean Berstel and Juhani Karhumäki. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 79:178-228, 2003.
• Combinatorics on Words: A New Challenging Topic, Juhani Karhumäki.
• Combinatorics of words, Christian Chorut, Juhani Karhumäki, in "Handbook of formal languages" volume 1, Grzegorz Rozenberg, Arto Salomaa, Springer, 1997, ISBN 9783540604204.
• Lothaire, M. (1983), Combinatorics on words, Encyclopedia of Mathematics and its Applications, 17, Addison-Wesley Publishing Co., Reading, Mass., ISBN 978-0-201-13516-9, MR675953, http://books.google.com/books?id=UV9_3plEr8wC 
• Lothaire, M. (2002), Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, 90, Cambridge University Press, ISBN 978-0-521-81220-7, MR1905123, http://www-igm.univ-mlv.fr/~berstel/Lothaire/AlgCWContents.html 
• "Infinite words: automata, semigroups, logic and games", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 9780125321112.
• Lothaire, M. (2005), Applied combinatorics on words, Encyclopedia of Mathematics and its Applications, 105, Cambridge University Press, ISBN 978-0-521-84802-2; 978-0-521-84802-2, MR2165687, http://www-igm.univ-mlv.fr/~berstel/Lothaire/AppliedCW/AppCWContents.html 
• "Algorithmic Combinatorics on Partial Words", Francine Blanchet-Sadri, CRC Press, 2008, ISBN 9781420060928.
• "Combinatorics on Words: Christoffel Words and Repetitions in Words", Jean Berstel, Aaron Lauve, Christophe Reutenauer, Franco V. Saliola, American Mathematical Society and Centre de Recherches Mathématiques, 2008, ISBN 9780821844809.
• "Combinatorics of Compositions and Words", Silvia Heubach, Toufik Mansour, CRC Press, 2009, ISBN 9781420072679.
• "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 9783540551249
• "Jewels of stringology: text algorithms", Maxime Crochemore, Wojciech Rytter, World Scientific, 2003, ISBN 9789810248970
• "Combinatorics, Automata and Number Theory", Valérie Berthé, Michel Rigo, Cambridge University Press, 2010, ISBN 9780521515979

External links

• Jean Berstel's page
• Tero Harju's page
• Guy Melançon's page

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Combinatorics on words Combinatorics stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Combinatorics and dynamical systems Parser combinator Look at other dictionaries: Combinatorics — is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain criteria can be met,… …   Wikipedia WORDS — Combinatorics on Words, ed. M. Lothaire, Encyclopedia of Mathematics and its Applications, Volume 17, Addison Wesley, 1983 (informationswissenschaftl. Veoeffentlichungen) …   Acronyms WORDS — Combinatorics on Words, ed. M. Lothaire, Encyclopedia of Mathematics and its Applications, Volume 17, Addison Wesley, 1983 (informationswissenschaftl. Veröffentlichungen) …   Acronyms von A bis Z Combinatorics and dynamical systems — The mathematical disciplines of combinatorics and dynamical systems interact in a number of ways. The ergodic theory of dynamical systems has recently been used to prove combinatorial theorems about number theory which has given rise to the field …   Wikipedia combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… …   Wikipedia Necklace (combinatorics) — In combinatorics, a k ary necklace of length n is an equivalence class of n character strings over an alphabet of size k, taking all rotations as equivalent. It represents a structure with n circularly connected beads of up to k different colors …   Wikipedia Symbolic combinatorics — in mathematics is a technique of analytic combinatorics that uses symbolic representations of combinatorial classes to derive their generating functions. The underlying mathematics, including the Pólya enumeration theorem, are explained on the… …   Wikipedia Bracelet (combinatorics) — In combinatorics, a k ary bracelet of length n is the equivalence class of all n character strings over an alphabet of size k , taking reverse and all rotations as equivalent. A bracelet, also referred to as a turnover necklace, represents a… …   Wikipedia Combinatoire des mots — Construction de la suite de Prouhet Thue Morse. La combinatoire des mots est une branche des mathématiques et de l informatique théorique qui applique l analyse combinatoire aux mots finis ou infinis. Cette branche s est développée à partir de… …   Wikipédia en Français 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”