Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Summary:
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.
References:
[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 1127191
[2] J. Ježek: Free groupoids in varieties determined by a short equation. Acta Univ. Carolinae 23 (1982), 3–24. MR 0678473
[3] J. Ježek and G.F. McNulty: Perfect bases for equational theories. to appear in J. Symbolic Computation. MR 1348785
Search
Partner of
