We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.

We generalize the notions of the degree and composition from uniquely decipherable codes to arbitrary finite sets of words. We prove that if X = Y∘Z is a composition of finite sets of words with Y complete, then d(X) = d(Y) ⋅ d(Z), where d(T) is the degree of T. We also show that a finite set is synchronizing if and only if its degree equals one. This is done by considering, for an arbitrary finite set X of words, the transition monoid of an automaton recognizing X^* with multiplicities. We prove a number of results for such monoids, which generalize corresponding results for unambiguous monoids of relations.

We study classes of minimal sets defined by restrictions on the possible extensions of the words. These sets generalize the previously studied classes of neutral and tree sets by relaxing the condition imposed on the empty word and measured by an integer called the characteristic of the set. We present several enumeration results holding in these sets of words. These formulae concern return words and bifix codes. They generalize formulae previously known for Sturmian sets or more generally for tree sets. We also give two geometric examples of this class of sets, namely the natural coding of some interval exchange transformations and the natural coding of some linear involutions.

A local automaton is by definition such that a bounded information about the past and the future is enough to determine the present state. Due to this synchronization property, these automata play an important role for coding purposes. We prove that any irreducible local automaton is contained in a complete one. The proof uses a result from symbolic dynamics due to M. Nasu called the masking lemma. A consequence of this result in the theory of variable length codes is that any locally parsable regular code is included in a maximal one with the same synchronisation delay.

The main result is a characterization of the generating sequences of the length of words in a regular language on k symbols. We say that a sequence s of integers is regular if there is a finite graph G with two vertices i, t such that s n is the number of paths of length n from i to t in G . Thus the generating sequence of a regular language is regular. We prove that a sequence s is the generating sequence of a regular language on k symbols if and only if both sequences s = ( s n ) n ≥0 and t = ( k n − s n ) n ≥0 are regular.

The main result is a finite-state version of the Kraft--McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new construction called the multiset construction, which is a version with multiplicities of the well-known subset construction of automata theory.

Several constructions are presented for extending a bounded-to-one sliding-block code to a bounded-to-one surjection onto its range, while preserving nice properties of the original code.

A new string-matching algorithm is presented, which can be viewed as an intermediate between the classical algorithms of Knuth, Morris, and Pratt on the one hand and Boyer and Moore, on the other hand.The algorithm is linear in time and uses constant space as the algorithm of Galil and Seiferas.It presents the advantage of being remarkably simple which consequently makes its analysis possible.The algorithm relies on a previously known result in combinatorics on words, called the Critical Factorization Theorem, which relates the global period of a word to Its local repetitions of blocks Categories and Subject Descriptors: D.

The purpose of automata theory is to study and classify those properties of words that may be defined by a finite structure, say a finite automaton or a finite monoid. It seems natural to consider the same problem for infinite words. This amounts to studying the asymptotic behaviour of finite automata. As is well-known, this breaks the equivalence between determinism and non-determinism of finite automata.