DOTD: Combinatorics on Words

2 Jan 2017

Combinatorics on words is the mathematical study of words, which is the foundation for stringology (algorithms on strings/words). The two main branches of this are:


1. Analysis of words

For example, a square-free word is a word in which no sub-word is a square. A square is a word of the form uu, where u is a sub-word which is repeated twice consecutively. When looking at a binary alphabet {a, b}, the only square-free words which can built upon this are a, b, ab, ba, aba and bab. The strings aa, bb, aab, abb, aaa, bbb, abab, baba (and so on) contain squares (in bold).

2. How words can be visualised

For example, the word banana can be represented by its suffix tree, shown below. (I will post a DOTD for suffix trees tomorrow!)



Share on Facebook
Share on Twitter
Share on LinkedIn
Please reload

Please reload

Related Posts
PhDomics by Fatima