We prove a long standing conjecture of Duval in the special case of Sturmian words.

Word and tree codes are studied in a common framework, that of polypodes which are sets endowed with a substitution like operation. Many examples are given and basic properties are examined. The code decomposition theorem is valid in this general setup.

We show that some natural refinements of the Straubing and Brzozowskihierarchies correspond (via the so called leaf-languages) step by step tosimilar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and thepolynomial hierarchies. In particular, this applies to the Boolean hierarchyand the plus-hierarchy.

The class of weak parallel machines is interesting, because it contains somerealistic parallel machine models, especially suitable for pipelinedcomputations. We prove that a modification of the bulk synchronous parallel(BSP) machine model, called decomposable BSP (dBSP), belongs to the class ofweak parallel machines if restricted properly. We will also correct someearlier results about pipelined parallel Turing machines.

For any finite word w on a finite alphabet, we consider the basic parameters Rw and Kw of w defined as follows: Rw is the minimal natural number for which w has no right special factor of length Rw and Kw is the minimal natural number for which w has no repeated suffix of length Kw. In this paper we study the distributions of these parameters, here called characteristic parameters, among the words of each length on a fixed alphabet.

The characteristic parameters K w and R w of a word w over a finite alphabet are defined as follows: K w is the minimal natural number such that w has no repeated suffix of length K w and R w is the minimal natural number such that w has no right special factor of length R w . In a previous paper, published on this journal, we have studied the distributions of these parameters, as well as the distribution of the maximal length of a repetition, among the words of each length on a given alphabet. In this paper we give the exact values of these distributions in a special case. However, these values give upper bounds to the distributions in the general case. Moreover, we study the most frequent and the average values of the characteristic parameters and of the maximal length of a repetition over the set of all words of length n.