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

DOI10.1016/J.TCS.2011.04.036zbMATH Open1223.68090arXiv0905.4923OpenAlexW2212932348MaRDI QIDQ638548FDOQ638548

Authors: James D. Currie 

Publication date: 12 September 2011

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

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.

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

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

zbMATH Keywords

combinatorics on wordsautomatic sequencesmorphic wordsRudin-Shapiro word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Periodicity, repetitions, and orbits of an automatic sequence
• Automatic Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure and extendibility of \(k\)-power free words

Cited In (3)

• Enumeration and decidable properties of automatic sequences
• Extremal words in morphic subshifts
• 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)