Jump to content

Combinatorics on words

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 89.242.185.100 (talk) at 07:05, 14 September 2010 (→‎References). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 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

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.
  • "Combinatorics on Words", M. Lothaire, Addison-Wesley, 1983, reprinted Cambridge University Press, 1997, ISBN 9780521599245.
  • "Algebraic Combinatorics on Words", M. Lothaire, Cambridge University Press, 2002, ISBN 9780521812207.
  • "Infinite words: automata, semigroups, logic and games", Dominique Perrin, Jean Éric Pin, Academic Press, 2004, ISBN 9780125321112.
  • "Applied Combinatorics on Words", M. Lothaire, Cambridge University Press, 2005, ISBN 9780521848022.
  • "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
Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "http://en.wiki.x.io/w/index.php?title=Combinatorics_on_words&oldid=384739852"