Codes avec des mots infinis
Codes limites et factorisations finies du monoïde libre
Commutative images of rational languages and the abelian kernel of a monoid
Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification of the algorithm...
Commutative images of rational languages and the Abelian kernel of a monoid
Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification of the algorithm...
Complément à l'étude des suites de Thue-Morse généralisées
Conjugacy in monoids.
Constructing finitely presented monoids which have no finite complete presentation.
Construction de codes indécomposables
Continuous monoids and yields of infinite trees
Crossability of cancellative Kleene semigroups
Decidability of periodicity for infinite words
Disjunctive languages and compatible orders
Disjunctive splittability of languages.
Disjunktive Teilmengen inverser Halbgruppen
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...
Distance desert automata and the star height problem
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...
Distinguishing subsets in lattices
Each regular code is included in a maximal regular code
Elementary ...-languages and finite semilattices of groups.
Equational description of pseudovarieties of homomorphisms
The notion of pseudovarieties of homomorphisms onto finite monoids was recently introduced by Straubing as an algebraic characterization for certain classes of regular languages. In this paper we provide a mechanism of equational description of these pseudovarieties based on an appropriate generalization of the notion of implicit operations. We show that the resulting metric monoids of implicit operations coincide with the standard ones, the only difference being the actual interpretation of pseudoidentities....