Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The problems of cyclic equality and conjugacy for finite complete rewriting systems
Narendran P., Otto F. Theoretical Computer Science47 (1):27-38,1986.Type:Article
Date Reviewed: Jun 1 1988

This paper continues the study of decision problems for finite complete rewriting systems [1]. The authors show that the problem of cyclic equality is undecidable for length-reducing finite complete rewriting systems. Their complicated proof, a combination of a construction and a characterization method, applies only to nonmonadic rewriting systems. The decidability of cyclic equality for finite monadic complete rewriting systems remains an open problem. Furthermore, whereas the left conjugacy problem and the conjugacy problem are decidable for length-reducing finite complete rewriting systems [2], the authors prove that these two problems are undecidable for general finite complete rewriting systems; the system T in the proof of Lemma 3.6 does not resolve this question.

Reviewer:  Adrian Atanasiu Review #: CR111709
1) Bauer, G., and Otto, F.Finite complete rewriting systems and the complexity of the word problem. Acta Inf.. 21 (1984), 521–540.
2) Narendran, P., and Otto, F.Complexity results on the conjugacy problem for monoids. Theor. Comput. Sci. 35 (1985), 227–243.
Bookmark and Share
 
Decision Problems (F.4.2 ... )
 
 
Parallel Rewriting Systems (F.4.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Decision Problems": Date
Ambiguity and decision problems concerning number systems
Karel I., Salomaa A. Information and Control 56(3): 139-153, 1983. Type: Article
Mar 1 1985
Parallel time O (log n) recognition of unambiguous context-free languages
Rytter W. Information and Computation 73(1): 75-86, 1987. Type: Article
Mar 1 1988
Fairness in term rewriting systems
Porat S., Francez N.  Rewriting techniques and applications (, Dijon, France,3001985. Type: Proceedings
Sep 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy