Geodesic
Some decidable congruences of free monoids
Czechoslovak Mathematical Journal, Tome 49 (1999) no. 3, pp. 475-480 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $W$ be the free monoid over a finite alphabet $A$. We prove that a congruence of $W$ generated by a finite number of pairs $\langle au,u\rangle $, where $a\in A$ and $u\in W$, is always decidable.
Let $W$ be the free monoid over a finite alphabet $A$. We prove that a congruence of $W$ generated by a finite number of pairs $\langle au,u\rangle $, where $a\in A$ and $u\in W$, is always decidable.
Classification : 03B25, 03C05, 08A30, 20M05 
@article{CMJ_1999_49_3_a1,
     author = {Je\v{z}ek, Jaroslav},
     title = {Some decidable congruences of free monoids},
     journal = {Czechoslovak Mathematical Journal},
     pages = {475--480},
     year = {1999},
     volume = {49},
     number = {3},
     mrnumber = {1707983},
     zbl = {1008.20049},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a1/}
}
TY  - JOUR
AU  - Ježek, Jaroslav
TI  - Some decidable congruences of free monoids
JO  - Czechoslovak Mathematical Journal
PY  - 1999
SP  - 475
EP  - 480
VL  - 49
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a1/
LA  - en
ID  - CMJ_1999_49_3_a1
ER  - 
%0 Journal Article
%A Ježek, Jaroslav
%T Some decidable congruences of free monoids
%J Czechoslovak Mathematical Journal
%D 1999
%P 475-480
%V 49
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a1/
%G en
%F CMJ_1999_49_3_a1
Ježek, Jaroslav. Some decidable congruences of free monoids. Czechoslovak Mathematical Journal, Tome 49 (1999) no. 3, pp. 475-480. http://geodesic.mathdoc.fr/item/CMJ_1999_49_3_a1/

[1] N. Dershowitz and J.-P. Jouannaud: Rewrite systems. Chapter 6, 243–320 in J. van Leeuwen, ed., Handbook of Theoretical Computer Science, B: Formal Methods and Semantics. North Holland, Amsterdam 1990. | MR

[2] J. Ježek: Free groupoids in varieties determined by a short equation. Acta Univ. Carolinae 23 (1982), 3–24. | MR

[3] J. Ježek and G.F. McNulty: Perfect bases for equational theories. to appear in J. Symbolic Computation. | MR