Name
Title | ||
|---|---|---|
Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids |
Abstract | ||
|---|---|---|
A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string-rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church–Rosser language. Finally we address the notion of left-regular convergent string-rewriting systems that are tractable. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1006/jsco.1998.0230 | J. Symb. Comput. |
Keywords | DocType | Volume |
infinite convergent | Journal | 26 |
Issue | ISSN | Citations |
5 | Journal of Symbolic Computation | 11 |
PageRank | References | Authors |
0.77 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Friederich Otto | 1 | 11 | 0.77 |
| M. Katsura | 2 | 58 | 10.49 |
| Yuji Kobayashi | 3 | 11 | 0.77 |