Extendibility and growth of words avoiding patterns

点击翻译按钮获取中文摘要

In the modern world, long sequences of symbols over small alphabets are of basic importance. Whether we are considering streams of 0's and 1's over the internet, or considering long DNA sequences made up from the letters A, C, G, T, understanding the mathematics of strings of symbols is of basic importance. This research studies the regularities and irregularities in long strings of symbols, identifying which patterns must always arise, and which can be avoided. The simplest patterns, repetitions, play a key role in data compression, such as we see every day in .zip files. More complicated patterns, involving repetitions and reversals, arise naturally in the study of genetic sequences in DNA or RNA, in so-called "DNA hairpins". Words avoiding patterns have also been proposed as a cryptographic tool. Simple questions about which patterns can be avoided in long strings of symbols remain unanswered, but problems which had been previously unsolved for 20 or 40 years are starting to be resolved. In the same way that studying simple objects in arithmetic, such as prime numbers, has led to technical breakthroughs in encryption of banking transactions, understanding the basic mathematics of strings of symbols should continue to have importance in data compression, genetic analysis and information technology.