On infinite prefix normal words

DOI10.1016/J.TCS.2021.01.015MaRDI QIDQ5919082zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Zsuzsanna Lipták, Massimiliano Rossi

Publication date 15 February 2021

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

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

zbMATH Keywords

combinatorics on wordslexicographic orderThue-Morse wordSturmian wordabelian complexityprefix normal wordpaperfolding word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• On infinite prefix normal words
• Weighted prefix normal words: mind the gap
• On prefix normal words
• On prefix normal words and prefix normal forms
• On collapsing prefix normal words

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 7428929 (Why is no real title available?)
• A Lower Bound for Jumbled Indexing
• Abelian complexity and frequencies of letters in infinite words
• Abelian complexity function of the Tribonacci word
• Abelian complexity of Thue-Morse word over a ternary alphabet
• Abelian complexity of minimal subshifts
• Algorithms for jumbled pattern matching in strings
• Binary bubble languages and cool-lex order
• Binary jumbled pattern matching on trees and tree-like structures
• Bubble-flip -- a new generation algorithm for prefix normal words
• Clustered Integer 3SUM via Additive Combinatorics
• Computing abelian complexity of binary uniform morphic words
• Efficient oracles for generating binary bubble languages
• Fast and simple jumbled indexing for binary run-length encoded strings
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Generating necklaces
• Inequalities characterizing standard Sturmian and episturmian words
• Infinite Lyndon words
• Leaf realization problem, caterpillar graphs and prefix normal words
• New algorithms for binary jumbled pattern matching
• On approximate jumbled pattern matching in strings
• On collapsing prefix normal words
• On combinatorial generation of prefix normal words
• On hardness of jumbled indexing
• On infinite prefix normal words
• On prefix normal words
• On prefix normal words and prefix normal forms
• On the asymptotic abelian complexity of morphic words
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• The abelian complexity of the paperfolding word
• The asymptotic number of prefix normal words

Cited in

(8)

• On collapsing prefix normal words
• Weighted prefix normal words: mind the gap
• On prefix normal words
• Bubble-flip -- a new generation algorithm for prefix normal words
• On prefix normal words and prefix normal forms
• Bubble-flip -- a new generation algorithm for prefix normal words
• The asymptotic number of prefix normal words
• On infinite prefix normal words

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: On infinite prefix normal words

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