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

DOI10.1016/J.JDA.2011.01.001MaRDI QIDQ414440zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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
• scientific article; zbMATH DE number 7559186 (Why is no real title available?)
• 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)