| 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 |
| . |
