Initial non-repetitive complexity of infinite words

DOI10.1016/J.DAM.2016.03.010MaRDI QIDQ284845zbMATHOpenAlexFDO

Authors Jeremy Nicholson, Narad Rampersad

Publication date 18 May 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Fibonacci wordinitial non-repetitive complexitysquarefree wordThue-Morse wordTribonacci word

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

Abstract: The initial non-repetitive complexity function of an infinite word x (first defined by Moothathu) is the function of n that counts the number of distinct factors of length n that appear at the beginning of x prior to the first repetition of a length-n factor. We examine general properties of the initial non-repetitive complexity function, as well as obtain formulas for the initial non-repetitive complexity of the Thue-Morse word, the Fibonacci word and the Tribonacci word.

Recommendations

• On non-repetitive complexity of Arnoux-Rauzy words
• A new complexity function for words based on periodicity
• Cyclic complexity of words
• scientific article; zbMATH DE number 7069796
• ON THE REPETITIVITY INDEX OF INFINITE WORDS

Cites work

• scientific article; zbMATH DE number 5707089 (Why is no real title available?)
• scientific article; zbMATH DE number 4085051 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 851423 (Why is no real title available?)
• A problem in arrangements
• Automatic Sequences
• Avoidable patterns in strings of symbols
• Avoiding squares and overlaps over the natural numbers
• Balance and abelian complexity of the Tribonacci word
• Enumeration and structure of trapezoidal words
• Eulerian entropy and non-repetitive subword complexity
• On extending de Bruijn sequences
• On highly repetitive and power free words
• Open and Closed Prefixes of Sturmian Words
• Palindrome complexity.
• Periodicity and the golden ratio
• Some properties of the Tribonacci sequence
• Uniformly growing k-th power-free homomorphisms

Cited in

(6)

• Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents
• On non-repetitive complexity of Arnoux-Rauzy words
• A new complexity function for words based on periodicity
• ON THE REPETITIVITY INDEX OF INFINITE WORDS
• scientific article; zbMATH DE number 1834659 (Why is no real title available?)
• The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word

This page was built for publication: Initial non-repetitive complexity of infinite words

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