The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n 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 n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More...

In this paper, we solve some open problems related to (pseudo)palindrome closure operators and to the infinite words generated by their iteration, that is, standard episturmian and pseudostandard words. We show that if ϑ is an involutory antimorphism of A*, then the right and left ϑ-palindromic closures of any factor of a ϑ-standard word are also factors of some ϑ-standard word. We also introduce the class of pseudostandard words with “seed”, obtained by iterated pseudopalindrome closure starting...

We study the functional equation: $\left(1\right)ABC=CDA$ where $A,B,C$ and $D$ are words over an alphabet $\mathcal{A}$. In particular we prove a «structure result» for the inner factors $B,D$: for suitably chosen words $X,Y,Z$ one has: $\left(2\right)B=XYZ$, $D=ZYX$$ 2 ⁢... On subgraphs without large components Glenn G. Chappell, John Gimbel (2017) Mathematica Bohemica We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring... On substitution invariant Sturmian words: an application of Rauzy fractals Valérie Berthé, Hiromi Ei, Shunji Ito, Hui Rao (2007) RAIRO - Theoretical Informatics and Applications Sturmian words are infinite words that have exactly n+1 factors of length n for every positive integer n. A Sturmian word sα,p is also defined as a coding over a two-letter alphabet of the orbit of point ρ under the action of the irrational rotation Rα : x → x + α (mod 1). A substitution fixes a Sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2001) RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly... On synchronized sequences and their separators Arturo Carpi, Cristiano Maggi (2010) RAIRO - Theoretical Informatics and Applications We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is... Currently displaying 41 – 60 of 129 Previous Page 3 Next $