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

DOI10.1016/J.JDA.2011.01.001zbMATH Open1253.68207OpenAlexW1985134476MaRDI QIDQ414440FDOQ414440

Authors: 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

Recommendations

• Subword complexity of a generalized Thue-Morse word
• On the structure of Thue-Morse subwords, with an application to dynamical systems
• On Subword Complexity of Morphic Sequences
• The subword complexity of polynomial subsequences of the Thue-Morse sequence
• On the subword complexity of Thue-Morse polynomial extractions
• Publication:4936661
• Usefulness of directed acyclic subword graphs in problems related to standard Sturmian words
• On generalized words of Thue-Morse
• scientific article; zbMATH DE number 4041316
• Subword complexity of the Fibonacci-Thue-Morse sequence: the proof of Dekking's conjecture

zbMATH Keywords

Thue-Morse wordcompacted subword graphgraph counting property

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• On Sensitivity of Compact Directed Acyclic Word Graphs
• Composite repetition-aware data structures
• Linear-size suffix tries and linear-size CDAWGs simplified and improved
• Title not available (Why is that?)
• Optimally computing compressed indexing arrays based on the compact directed acyclic word graph

This page was built for publication: On the structure of compacted subword graphs of Thue-Morse words and their applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414440)