# Article

 Title: Some decidable congruences of free monoids (English) Author: Ježek, Jaroslav Language: English Journal: Czechoslovak Mathematical Journal ISSN: 0011-4642 (print) ISSN: 1572-9141 (online) Volume: 49 Issue: 3 Year: 1999 Pages: 475-480 Summary lang: English . Category: math . 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. (English) MSC: 03B25 MSC: 03C05 MSC: 08A30 MSC: 20M05 idZBL: Zbl 1008.20049 idMR: MR1707983 . Date available: 2009-09-24T10:24:30Z Last updated: 2020-07-03 Stable URL: http://hdl.handle.net/10338.dmlcz/127503 . Reference: [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 Reference: [2] J. Ježek: Free groupoids in varieties determined by a short equation.Acta Univ. Carolinae 23 (1982), 3–24. MR 0678473 Reference: [3] J. Ježek and G.F. McNulty: Perfect bases for equational theories.to appear in J. Symbolic Computation. MR 1348785 .

## Files

Files Size Format View
CzechMathJ_49-1999-3_2.pdf 293.8Kb application/pdf View/Open

Partner of