For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
Classically, in order to resolve an equation over a free monoid , we reduce it by a suitable family of substitutions to a family of equations , , each involving less variables than , and then combine solutions of into solutions of . The problem is to get in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to . We carry out such a parametrization in the case the prime equations in the graph...
Classically, in order to resolve an equation u ≈ v over a free monoid X*, we reduce it by a suitable family of substitutions to a family of equations uf ≈ vf, , each involving less variables than u ≈ v, and then combine solutions of uf ≈ vf into solutions of u ≈ v. The problem is to get in a handy parametrized form. The method we propose consists in parametrizing the path traces in the so called graph of prime equations associated to u ≈ v. We carry out such a parametrization in the case the...
We divide infinite sequences of subword complexity 2n+1 into four subclasses with respect to left and right special elements and examine the structure of the subclasses with the help of Rauzy graphs. Let k ≥ 2 be an integer. If the expansion in base k of a number is an Arnoux-Rauzy word, then it belongs to Subclass I and the number is known to be transcendental. We prove the transcendence of numbers with expansions in the subclasses II and III.
We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In particular,...