We analyze an algorithm that decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in , where is the length of the word and the size of the alphabet.
Rauzy fractals are compact sets with fractal boundary that can be associated with any unimodular Pisot irreducible substitution. These fractals can be defined as the Hausdorff limit of a sequence of compact sets, where each set is a renormalized projection of a finite union of faces of unit cubes. We exploit this combinatorial definition to prove the connectedness of the Rauzy fractal associated with any finite product of three-letter Arnoux–Rauzy substitutions.
A deterministic automaton recognizing a given ω-regular language is constructed from an ω-regular expression with the help of derivatives. The construction is related to Safra's algorithm, in about the same way as the classical derivative method is related to the subset construction.
The main purpose of this work is to present new families of transcendental continued fractions with bounded partial quotients. Our results are derived thanks to combinatorial transcendence criteria recently obtained by the first two authors in [3].
We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.
We add a sufficient condition for validity of Propo- sition 4.10 in the paper Frougny et al. (2004). This condition is not a necessary one, it is nevertheless convenient, since anyway most of the statements in the paper Frougny et al. (2004) use it.
An algorithm is corrected here that was presented as Theorem 2 in [Š. Holub, RAIRO-Theor. Inf. Appl. 40 (2006) 583–591]. It is designed to calculate the maximum length of a nontrivial word with a given set of periods.
An algorithm is corrected here that was presented as Theorem 2 in [Š. Holub, RAIRO-Theor. Inf. Appl. 40 (2006) 583–591]. It is designed to calculate the maximum length of a nontrivial word with a given set of periods.