On the structure of compacted subword graphs of Thue-Morse words and their applications

详细信息    查看全文

• 作者：Jakub Radoszewski ; ^{jrad@mimuw.edu.pl} ; Wojciech Rytter ^{rytter@mimuw.edu.pl}
• 关键词：Thue&ndash ; Morse word ; Compacted subword graph ; Graph counting property
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 出版时间：February 2012
• 年：2012
• 卷：11
• 期：Complete
• 页码：15-24
• 全文大小：475 K

文摘

We investigate how syntactic properties of Thue-Morse words are related to special type of automata/graphs. The directed acyclic subword graph (dawg, in short) is a useful deterministic automaton accepting all suffixes of the word. Its compacted version (resulted by compressing chains of states) is denoted by cdawg. The cdawgs of Thue-Morse words have regular and very simple structure, in particular they offer a powerful (exponential) compression of the set of all subwords in case of finite Thue-Morse words. Using the special structure of cdawgs we present several unknown properties of Thue-Morse words as well as new (graph-based) proofs of some well-known properties. In particular we show a simple algorithm that checks, for a given string w, if w is a subword of a Thue-Morse word and computes its number of occurrences in n-th Thue-Morse word in time and space. Additionally, a slight modification of the compact dawg of the infinite Thue-Morse word yields an infinite graph with 2-counting property.