Compressed string-matching in standard Sturmian words

DOI10.1016/j.tcs.2009.03.007zbMath1173.68045OpenAlexW2001438476MaRDI QIDQ2271418

Paweł Baturo, Wojciech Rytter

Publication date: 7 August 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.007

zbMATH Keywords

Sturmian wordslinear timestring-matchinglexicographic numeration property

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (5)

A simple representation of subwords of the Fibonacci word ⋮ A combinatorial view on string attractors ⋮ Computing the number of cubic runs in standard Sturmian words ⋮ Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts ⋮ A characterization of finite arithmetic progressions via regular partitions of quadrilaterals

Cites Work

• Burrows-Wheeler transform and Sturmian words
• Sturmian words: structure, combinatorics, and their arithmetics
• Characterisations of balanced words via orderings
• A new characteristic property of the palindrome prefixes of a standard Sturmian word
• Inequalities characterizing standard Sturmian and episturmian words
• Indexing compressed text
• The Number of Runs in Sturmian Words
• USEFULNESS OF DIRECTED ACYCLIC SUBWORD GRAPHS IN PROBLEMS RELATED TO STANDARD STURMIAN WORDS
• A remark on morphic sturmian words
• Automatic Sequences
• Jewels of Stringology
• Suffix Automata and Standard Sturmian Words
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item

This page was built for publication: Compressed string-matching in standard Sturmian words