Displaying similar documents to “Sequences of low arithmetical complexity”

On possible growths of arithmetical complexity

Anna E. Frid (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length . In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions....

Some Algebraic Properties of Machine Poset of Infinite Words

Aleksandrs Belovs (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Sturmian jungle (or garden?) on multiliteral alphabets

L'ubomíra Balková, Edita Pelantová, Štěpán Starosta (2010)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The properties characterizing sturmian words are considered for words on multiliteral alphabets. We summarize various generalizations of sturmian words to multiliteral alphabets and enlarge the list of known relationships among these generalizations. We provide a new equivalent definition of rich words and make use of it in the study of generalizations of sturmian words based on palindromes. We also collect many examples of infinite words to illustrate differences in the generalized...