We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be Θ(n4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov [Problemy Kibernet. 39 (1982) 67–84], then independently by Mignosi [Theoret. Comput. Sci. 82 (1991) 71–84], and others.

In the literature various types of restarting automata have been studied that are basedon contextual rewriting. A word w is accepted by such an automaton if,starting from the initial configuration that corresponds to input w, theword w is reduced to the empty word by a finite number of applications ofthese contextual rewritings. This approach is reminiscent of the notion of McNaughtonfamilies of languages. Here we put the aforementioned types of restarting automata intothe context of McNaughton families of languages, relating the classes of languagesaccepted by these automata in particular to the class GCSL of growing context-sensitivelanguages and to the class CRL of Church–Rosser languages.

We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.

A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.

The recently introduced model of transducing by observing is compared with traditionalmodels for computing transductions on the one hand and the recently introduced restartingtransducers on the other hand. Most noteworthy, transducing observer systems withlength-reducing rules are almost equivalent to RRWW-transducers. With painter rules weobtain a larger class of relations that additionally includes nearly all rationalrelations.

Pattern avoidance is an important topic in combinatorics on words which dates back to the beginning of the twentieth century when Thue constructed an infinite word over a ternary alphabet that avoids squares, i.e., a word with no two adjacent identical factors. This result finds applications in various algebraic contexts where more general patterns than squares are considered. On the other hand, Erdős raised the question as to whether there exists an infinite word that avoids abelian squares, i.e., a word with no two adjacent factors being permutations of one another. Although this question was answered affirmately years later, knowledge of abelian pattern avoidance is rather limited. Recently, (abelian) pattern avoidance was initiated in the more general framework of partial words, which allow for undefined positions called holes. In this paper, we show that any pattern p with n> 3 distinct variables of length at least 2n is abelian avoidable by a partial word with infinitely many holes, the bound on the length of p being tight. We complete the classification of all the binary and ternary patterns with respect to non-trivial abelian avoidability, in which no variable can be substituted by only one hole. We also investigate the abelian avoidability indices of the binary and ternary patterns.

Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC)proposed in the 90s of the last century. The uninspiring and arid language then used,condemned these works to oblivion. Although some of these schemes were afterwards shown tobe insecure, the promise of a new system of PKC relying on different complexityassumptions is still quite exciting. The algorithms there used depend heavily on theresults of invertibility of linear transducers. In this paper we introduce the notion ofpost-initial linear transducer, which is an extension of the notion of linear finitetransducer with memory, and for which the previous fundamental results on invertibilitystill hold. This extension enabled us to give a new method to obtain a left inverse of anyinvertible linear finite transducer with memory. It also plays an essencial role in thenecessary and sufficient condition that we give for left invertibility of linear finitetransducers.

We consider numeration systems with base β and − β, for quadratic Pisot numbers β and focus on comparing the combinatorial structure of the sets Zβ and Z− β of numbers with integer expansion in base β, resp. − β. Our main result is the comparison of languages of infinite words uβ and u− β coding the ordering of distances between consecutive β- and (− β)-integers. It turns out that for a class of roots β of x2 − mx − m, the languages coincide, while for other quadratic Pisot numbers the language of uβ can be identified only with the language of a morphic image of u− β. We also study the group structure of (− β)-integers.

We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular languages. Essentially, we prove that the hierarchy of language families obtained from conditional Lindenmayer systems with subregular conditions is almost identical to the hierarchy of families of subregular languages.