Cet article est une introduction aux aspects combinatoires de la distance -adique et de la topologie -adique sur les mots. On donne plusieurs définitions équivalentes de ces notions, illustrées par divers exemples et propriétés. Après avoir décrit de façon détaillée les ouverts, on démontre que la distance -adique est uniformément équivalente à une distance obtenue à partir des coefficients binomiaux définis sur les mots. On donne également deux exemples de suites convergentes dans la topologie...
In an earlier paper, the second author generalized Eilenberg’s variety theory by establishing a basic correspondence between certain classes of monoid morphisms and families of regular languages. We extend this theory in several directions. First, we prove a version of Reiterman’s theorem concerning the definition of varieties by identities, and illustrate this result by describing the identities associated with languages of the form , where are distinct letters. Next, we generalize the notions...
In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case. Another...
In a previous paper, the authors studied the polynomial closure of
a variety of languages and gave an algebraic counterpart, in terms
of Mal'cev products, of this operation. They also formulated a
conjecture about the algebraic counterpart of the boolean closure
of the polynomial closure – this operation corresponds to
passing to the upper level in any concatenation hierarchy.
Although this conjecture is probably true in some particular
cases, we give a counterexample in the general case....
In an earlier paper, the second author generalized Eilenberg's
variety theory by establishing a basic correspondence between
certain classes of monoid morphisms and families of regular
languages. We extend this theory in several directions. First, we
prove a version of Reiterman's theorem concerning the definition of
varieties by identities, and illustrate this result by describing
the identities associated with languages of the form
, where are distinct letters. Next,...
Download Results (CSV)