Let p be a prime number and let G_p be the variety of all languages recognised by a finite p-group. We give a construction process of all G_p-preserving functions from a free monoid to a free group. Our result follows from a new noncommutative generalization of Mahler’s theorem on interpolation series, a celebrated result of p-adic analysis.

We present a comparative study of four product operators on weighted languages: (i) the convolution, (ii) the shuffle, (iii) the infiltration and (iv) the Hadamard product. Exploiting the fact that the set of weighted languages is a final coalgebra, we use coinduction to prove that an operator of the classical difference calculus, the Newton transform, generalises from infinite sequences to weighted languages. We show that the Newton transform is an isomorphism of rings that transforms the Hadamard product of two weighted languages into their infiltration product, and we develop various representations for the Newton transform of a language, together with concrete calculation rules for computing them.

Regular cost functions were introduced as a quantitative generalisation of regular languages, retaining many of their equivalent characterisations and decidability properties. For instance, stabilisation monoids play the same role for cost functions as monoids do for regular languages. The purpose of this article is to further extend this algebraic approach by generalising two results on regular languages to cost functions: Eilenberg's varieties theorem and profinite equational characterisations of lattices of regular languages. This opens interesting new perspectives, but the specificities of cost functions introduce difficulties that prevent these generalisations to be straightforward. In contrast, although syntactic algebras can be defined for formal power series over a commutative ring, no such notion is known for series over semirings and in particular over the tropical semiring.

This survey paper presents the success story of the topological approach to automata theory. It is based on profinite topologies, which are built from finite topogical spaces. The survey includes several concrete applications to automata theory.

In this paper, we prove an extension of Mahler's theorem, a celebrated result of $p$-adic analysis. Mahler's original result states that a function from $N$ to $Z$ is uniformly continuous for the $p$-adic metric $d_p$ if and only if it can be uniformly approximated by polynomial functions. We prove the same result for functions from $A^*$ to $Z$, where $d_p$ is now the profinite metric defined by $p$-groups (pro-$p$ metric).

Two results by Schutzenberger (1965) and by Mc- Naughton and Papert (1971) lead to a precise description of the expressive power of first order logic on words interpreted as ordered colored structures. In this paper, we study the expressive power of existential formulas and of Boolean combinations of existential formulas in a logic enriched by modular numerical predicates. We first give a combinatorial description of the corresponding regular languages, and then give an algebraic characterization in terms of their syntactic morphisms. It follows that one can effectively decide whether a given regular language is captured by one of these two fragments of first order logic. The proofs rely on nontrivial techniques of semigroup theory: stamps, derived categories and wreath products.

We give a sufficient condition under which the least fixpoint of the equation X=a+f(X)X equals the least fixpoint of the equation X=a+f(a)X. We then apply that condition to recursive logic programs containing chain rules: we translate it into a sufficient condition under which a recursive logic program containing n/spl ges/2 recursive calls in the bodies of the rules is equivalent to a linear program containing at most one recursive call in the bodies of the rules. We conclude with a discussion comparing our condition with the other approaches to linearization studied in the literature.>