Previous |  Up |  Next


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:
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 appear in J. Symbolic Computation. MR 1348785


Files Size Format View
CzechMathJ_49-1999-3_2.pdf 293.8Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo