On possible growths of Toeplitz languages

DOI10.1134/S0037446606010071zbMATH Open1215.68191arXiv1003.1489OpenAlexW2112509991MaRDI QIDQ536628FDOQ536628

F. V. Petrov, Julien Cassaigne, Anna Frid

Publication date: 19 May 2011

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Complexity and special factors
• Complexity of sequences and dynamical systems
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Complexity of Toeplitz sequences
• Title not available (Why is that?)
• Arithmetical complexity of symmetric D0L words.
• On possible growths of arithmetical complexity
• Constructing Infinite Words of Intermediate Arithmetical Complexity
• Sequences of linear arithmetical complexity
• On the Linear Independence of Fractional Powers of Integers

Cited In (3)

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

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)