Lexicographically least words in the orbit closure of the Rudin-Shapiro word

DOI10.1016/J.TCS.2011.04.036MaRDI QIDQ638548zbMATH OpenOpenAlexFDO

Authors James D. Currie

Publication date 12 September 2011

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

Full work available at URL https://arxiv.org/abs/0905.4923

zbMATH Keywords

automatic sequencescombinatorics on wordsmorphic wordsRudin-Shapiro word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We give an effective characterization of the lexicographically least word in the orbit closure of the Rudin-Shapiro word w having a specified prefix. In particular, the lexicographically least word in the orbit closure of the Rudin-Shapiro word is 0w. This answers a question Allouche et al.

Recommendations

• Extremal words in the shift orbit closure of a morphic sequence
• A tighter bound for the number of words of minimum length in an automorphic orbit.
• Counting words of minimum length in an automorphic orbit.
• An extension of the Lyndon-Schützenberger result to pseudoperiodic words
• An Extension of the Lyndon Schützenberger Result to Pseudoperiodic Words
• Unary Words Have the Smallest Levenshtein k-Neighbourhoods
• A periodicity lemma for partial words
• On periodicity lemma for partial words
• Schützenberger and Eilenberg theorems for words on linear orderings
• Developments in Language Theory

Cites work

• Automatic Sequences
• scientific article; zbMATH DE number 992016 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• On the structure and extendibility of \(k\)-power free words
• Periodicity, repetitions, and orbits of an automatic sequence

Cited in

(3)

• Extremal words in morphic subshifts
• Enumeration and decidable properties of automatic sequences
• Extremal words in the shift orbit closure of a morphic sequence

This page was built for publication: Lexicographically least words in the orbit closure of the Rudin-Shapiro word

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