Combinatorics on Words Bibliography

prepared by:
Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, New York 11451-0001

Email: (for additions, suggestions, and corrections)


This bibliography is broader than some might take the combinatorics on words area to be in that it includes references to materials about string manipulation and combinatorial pattern matching.

Allouche, J-P. and J. Shallit. The ubiquitous prouhet-thue-morse sequence, in Sequences and their applications, pp. 1-16. Springer, London, 1999.

Allouche, J-P. and J. Shallit. Sums of Digits, Overlaps, and Palindromes, Discrete Mathematics & Theoretical Computer Science 4 (2000) 1-10.

Allouche, J.-P. and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge, 2003.

Berstel, J., Axel Thue's work on repetitions in words, Series formelles et combinatoire algebrique 11 (1992) 65-80.

Berstel, J. and L. Boasson, Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci. 218 (1999) 135-141.

Berstel, J. and J. Karhumaki, Combinatorics on words: A tutorial, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 79 (2003) 178-228.

Berstel, J., Axel Thue's work on repetitions in words. In P. Leroux, C. Reutenauer (Eds.) Series Formelles et Combinatoire Algebrique (Number 11 in Publications du LACIM, Universite du Quebec - Montreal, 1992), pp 65-80.

Berstel, J. and D. Perrin, The origins of combinatorics on words, European Journal of Combinatorics 28 (2007) 996-1022.

Chao, K-M. and L. Zhang, Sequence Comparsion, Springer, New York, 2009.

Crochemore, M., Sharp characterizations of squarefree morphisms, Theoret. Comput. Sci. 18 (1982) 221-226.

Crochemore, M. and D. Perrin, Two-way string matching, J. ACM 38, 651-675, 1991.

Crochemore, M. and W. Rytter, Jewels of Stringology, World Scientific, 2002.

Crochemore, M. and W. Rytter, Text Algorithms, Oxford University Press, 1994.

Crochmore, M. and C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge U. Press, 2007.

Farach-Colton, M., (ed.), Combinatorial Pattern Matching, Lecture Notes in Computer Science, Volume 1448, Springer, New York, 1998.

Fine, N. and H. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 1965 109114.

Gusfield, D., Algorithms on Strings, Trees, and Sequences, Cambridge U. Press, New York, 1997.

Lothaire, M., Combinatorics on Words, Addison-Wesley, 1983.

Lothaire, M., Algebraic Combinatorics on Words, Cambridge University Press, New York, 2002.

Lothaire, M. Applied Combinatorics on Words, Cambridge U. Press, New York, 2005.

Louck, J., Problems in combinatorics on words originating from discrete systems, Ann. Comb., 1 (1997) 99-104.

Morse, M., Recurrent geodesics on a surface of negative curvature, Trans. Am. Math. Soc. 22 (1921) 84-100.

M. Morse, A solution of the problem of infinite play in chess, Bull. Am. Math. Soc., 44 (1938) 632.

M. Morse and G. Hedlund, Symbolic dynamics, Am. J. Math. 60, (1938) 815-866.

Nagell, T., and A. Selberg, S. Selberg, K. Thalberg. Selected mathematical papers of Axel Thue. Universitetsforlaget, Oslo, 1977.

Navarro, G. and M Raffinot, Flexible Pattern Matching in Strings, Cambridge U. Press, New York, 2002.

Offner, C., Repetitions of words and the Thue-Morse sequence. (Preprint)

Palacios-Huerta, I., Tournaments, fairness and the prouhet-thue-morse sequence, Economic inquiry 50 (2012) 848-849.

Seebold, P ., On some generalizations of the Thue-Morse morphism, Theoretical computer science 292, (2003) 283-298.

Shallit, J., A second course in formal languages and automata theory, Vol. 179. Cambridge: Cambridge University Press, New York, 2009.

Thue, A., Uber unendliche Zeichenreihen, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana, Nr. 7, 1906.

Thue, A., Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana, Nr. 12, 1912.

Springer in its Lecture Notes in Computer Science series has published conference proceedings devoted to Combinatorial Pattern Matching. These books have many articles that deal with combinatorics on words.

Back to list of bibliographies