Combinatorics on Words: A New Challenging Topic1

Combinatorics on Words is a relatively new research topic in discrete math-ematics, mainly, but not only, motivated by computer science. In this paper we have three major goals. First, starting from very basic definitions we move via some typical proof techniques of the theory to a simply formulated open problems. Second, we discuss a few highlights of the theory, and finally we concentrate to connections between combinatorics on words and other branches of mathematics. 1Supported by the Academy of Finland under the grant 44087. Combinatorics on Words (CoW in short) is a relatively new rapidly grow-ing area of discrete mathematics. Its main object is a word, i.e. a sequence – either finite or infinite – of symbols taken from a finite set, usually re-ferred to as an alphabet. The natural environment of a word is that of a free monoid. Consequently, noncommutativity is a fundamental feature of words. Indeed, the words like “no ” and “on ” are not equal