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

DOI10.1016/j.jda.2011.01.001zbMath1253.68207OpenAlexW1985134476MaRDI QIDQ414440

Jakub Radoszewski, Wojciech Rytter

Publication date: 11 May 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.01.001

zbMATH Keywords

Thue-Morse wordcompacted subword graphgraph counting property

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Composite Repetition-Aware Data Structures ⋮ On Sensitivity of Compact Directed Acyclic Word Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Subword complexity of a generalized Thue-Morse word
• The structure of subword graphs and suffix trees of Fibonacci words
• On Sturmian graphs
• The smallest automaton recognizing the subwords of a text
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• On bispecial factors of the Thue-Morse word
• On-line construction of compact directed acyclic word graphs
• Enumeration of factors in the Thue-Morse word
• Reducing space for index implementation.
• Combinatorics on Words
• Jewels of Stringology