On the structure of compacted subword graphs of Thue–Morse words and their applications
| Autor: | Wojciech Rytter, Jakub Radoszewski |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Compacted subword graph Mathematics::Combinatorics Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Mathematical proof Morse code Graph Exponential function Automaton law.invention Theoretical Computer Science Combinatorics Graph counting property Thue–Morse word Computational Theory and Mathematics Deterministic automaton law Computer Science::Discrete Mathematics Discrete Mathematics and Combinatorics SIMPLE algorithm Computer Science::Formal Languages and Automata Theory Directed acyclic word graph Mathematics |
| Zdroj: | Journal of Discrete Algorithms. 11:15-24 |
| ISSN: | 1570-8667 |
| DOI: | 10.1016/j.jda.2011.01.001 |
| Popis: | 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 O(|w|+logn) time and O(1) space. Additionally, a slight modification of the compact dawg of the infinite Thue–Morse word yields an infinite graph with 2-counting property. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect