×

zbMATH — the first resource for mathematics

Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group. (English) Zbl 0555.20036
Author’s abstract: ”It is shown that for the presentation (a,b; \(abbaab=\lambda)\) of the Jantzen monoid J no finite complete rewriting system exists that is based on a Knuth-Bendix ordering. However, a finite complete rewriting system is given for a different presentation of J that has four generators. Further, a finite complete rewriting system is given for the presentation (a,b,c; \(abc=cba)\) of the Greendlinger group G. This system induces a polynomial-time algorithm for the word problem for G.”
Reviewer: B.Pondelíček

MSC:
20M05 Free semigroups, generators and relations, word problems
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avenhaus, J.; Madlener, K., Subrekursive komplexität bei gruppen, I. gruppen mit vorgechriebener komplexität, Acta inform., 9, 87-104, (1977) · Zbl 0371.02019
[2] Avenhaus, J.; Book, R.; Squier, C., On expressing commutativity by finite church-rosser presentations: A note on commutative monoids, RAIRO inform. theor., 18, 47-52, (1984) · Zbl 0542.20038
[3] Bauer, G., Zur darstellung von monoiden durch konfluente regelsysteme, ()
[4] Book, R.; Ó’Dúnlaing, C., Testing for the church-rosser property, Theoret. comput. sci., 16, 223-229, (1981) · Zbl 0479.68035
[5] Book, R., Confluent and other types of thue systems, J. assoc. comput. Mach., 29, 171-182, (1982) · Zbl 0478.68032
[6] Book, R., When is a monoid a group? the church-rosser case is tractable, Theoret. comput. sci., 18, 325-331, (1982) · Zbl 0489.68021
[7] Book, R., The power of the church-rosser property in string rewriting systems, Proc. 6th conf. on automated deduction, 360-368, (1982)
[8] Buchberger, B.; Loos, R., Algebraic simplification, () · Zbl 0494.68045
[9] Dershowitz, N., Orderings for term-rewriting systems, Theoret. comput. sci., 17, 279-301, (1982) · Zbl 0525.68054
[10] Dershowitz, N., Applications of the Knuth-bendix completion procedure, ()
[11] Greendlinger, M., Dehn’s algorithm for the word problem, Comm. pure appl. math., 13, 67-83, (1960) · Zbl 0104.01903
[12] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. assoc. comput. Mach., 27, 797-821, (1980) · Zbl 0458.68007
[13] Huet, G.; Lankford, D.S., On the uniform halting problem for term rewriting systems, ()
[14] Huet, G.; Oppen, D., Equations and rewrite rules—a survey, ()
[15] Jantzen, M., On a special monoid with a single defining relation, Theoret. comput. sci., 16, 61-73, (1981) · Zbl 0482.20043
[16] Jantzen, M., Semi-thue systems and generalised church-rosser properties, (), 60-75
[17] Kemmerich, S., Unendliche reduktionssysteme, Dissertation, (1983), TH Aachen · Zbl 0619.68034
[18] Knuth, D.; Bendix, P., Simple word problems in universal algebra, () · Zbl 0188.04902
[19] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[20] Lescanne, P., Analysis of data structures with non-distinct keys, (), Note · Zbl 0516.68020
[21] Lyndon, R.; Schupp, P., Combinatorial group theory, (1977), Springer Berlin · Zbl 0368.20023
[22] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1976), Dover New York
[23] Narendran, P.; McNaughton, R., The undecidability of the preperfectness of thue systems, Theoret. comput. sci., 31, 1, 2, 165-174, (1984) · Zbl 0545.03022
[24] Nivat, M., Congruences parfaites et quasi-parfaites, Séminaire dubreuil, 7, (1971-1972) · Zbl 0338.02018
[25] Potts, D., Remarks on an example of jantzen, Theoret. comput. sci., 29, 3, 277-284, (1984) · Zbl 0538.03034
[26] Squier, C.; Wrathall, C., A note on representations of a certain monoid, Theoret. comput. sci., 17, 229-231, (1982) · Zbl 0473.20044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.