Initial non-repetitive complexity of infinite words

DOI10.1016/J.DAM.2016.03.010zbMATH Open1342.68262arXiv1507.08206OpenAlexW2962837101MaRDI QIDQ284845FDOQ284845

Authors: Jeremy Nicholson, Narad Rampersad 

Publication date: 18 May 2016

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

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.

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

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

zbMATH Keywords

Fibonacci wordinitial non-repetitive complexitysquarefree wordThue-Morse wordTribonacci word

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• ON THE REPETITIVITY INDEX OF INFINITE WORDS
• Title not available (Why is that?)
• The periodic complexity function of the Thue-Morse word, the Rudin-Shapiro word, and the period-doubling word
• Initial nonrepetitive complexity of regular episturmian words and their Diophantine exponents
• A new complexity function for words based on periodicity
• On non-repetitive complexity of Arnoux-Rauzy words

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)