On possible growths of Toeplitz languages

DOI10.1134/S0037446606010071MaRDI QIDQ536628zbMATH OpenOpenAlexFDO

Authors Julien Cassaigne, Anna Frid, F. V. Petrov

Publication date 19 May 2011

Published in Siberian Mathematical Journal (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsTauberian theoremssubword complexityasymptotic combinatoricsToeplitz wordsanalytical methods in combinatoricsarithmetical complexityWiener-Pitt theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Abstract: We consider a new family of factorial languages whose subword complexity grows as $Theta(n^{alpha})$, where $alpha$ is the root of some transcendent equation. Analytical methods and in particular, a corollary of the Wiener-Pitt theorem, are used to find the asymptotic growth of the complexity. Factorial languages considered are languages of arithmetical factors of some Toeplitz words. So, we describe a new family of words with an unusual growth of arithmetical complexity.

Recommendations

• On possible growths of arithmetical complexity
• Factorial languages with quadratically upper bounded growth functions and nonlinearly upper bounded subword complexities
• Factorial Languages of Low Combinatorial Complexity
• On the growth rates of complexity of threshold languages
• Growth rates of complexity of power-free languages

Cites work

• scientific article; zbMATH DE number 1186086 (Why is no real title available?)
• scientific article; zbMATH DE number 1948496 (Why is no real title available?)
• scientific article; zbMATH DE number 2142718 (Why is no real title available?)
• Arithmetical complexity of symmetric D0L words.
• Complexity and special factors
• Complexity of Toeplitz sequences
• Complexity of sequences and dynamical systems
• Constructing Infinite Words of Intermediate Arithmetical Complexity
• On possible growths of arithmetical complexity
• On the Linear Independence of Fractional Powers of Integers
• Sequences of linear arithmetical complexity
• Toeplitz words, generalized periodicity and periodically iterated morphisms

Cited in

(3)

• On possible growths of arithmetical complexity
• Comparing Complexity Functions of a Language and Its Extendable Part
• LANGUAGES WITH A FINITE ANTIDICTIONARY: SOME GROWTH QUESTIONS

This page was built for publication: On possible growths of Toeplitz languages

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