The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems

1. B. Benninghofen, S. Kemmerich, M. M. Richter,Systems of Reductions, Lecture Notes in Computer Science, Vol. 277, Springer-Verlag, Berlin, 1987.

   Google Scholar 

2. R. V. Book, Confluent and other types of Thue systems,Journal of the Association for Computing Machinery 29 (1982), 171–182.

   Google Scholar 

3. R. V. Book, Decidable sentences of Church-Rosser congruences,Theoretical Computer Science 23 (1983), 301–312.

   Google Scholar 

4. R. V. Book, Thue systems as rewriting systems,Journal of Symbolic Computation 3 (1987), 39–68.

   Google Scholar 

5. R. V. Book, C. O'Dunlaing, Testing for the Church-Rosser property,Theoretical Computer Science 16 (1981), 223–229.

   Google Scholar 

6. H. Bücken, Reduction systems and small cancellation theory,Proceedings of the 4th Workshop on Automated Deduction (1979), pp. 53–59.

7. R. H. Gilman, Presentations of groups and monoids,Journal of Algebra 57 (1979), 544–554.

   Google Scholar 

8. J. E. Hopcroft, J. D. Ullman,Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979.

   Google Scholar 

9. M. Jantzen,Confluent String Rewriting, Springer-Verlag, Berlin, 1988.

   Google Scholar 

10. D. Kapur, M. S. Krishnamoorthy, R. F. McNaughton, P. Narendran, AnO(¦T¦³) algorithm for testing the Church-Rosser property of Thue systems,Theoretical Computer Science 35 (1985), 109–114.

    Google Scholar 

11. Ph. LeChenadec,Canonical Forms in Finitely Presented Algebras, Pitman, London, Wiley, New York, 1986.

    Google Scholar 

12. R. C. Lyndon, P. E. Schupp,Combinatorial Group Theory, Springer-Verlag, Berlin, 1977.

    Google Scholar 

13. K. Madiener, P. Narendran, F. Otto, A specialized completion procedure for monadic string-rewriting systems presenting groups, in: J. Leach Albert, B. Monien, M. Rodriguez Artalejo (eds.),Automata, Languages, and Programming, Proceedings of the 18th International Colloquium, Lecture Notes in Computer Science, Vol. 510, Springer-Verlag, Berlin, 1991, pp. 279–290.

    Google Scholar 

14. K. Madiener, F. Otto, Using string-rewriting for solving the word problem for finitely presented groups,Information Processing Letters 24 (1987), 281–284.

    Google Scholar 

15. R. F. McNaughton, P. Narendran, Special monoids and special Thue systems,Journal of Algebra 108 (1987), 248–255.

    Google Scholar 

16. F. Otto, On deciding the confluence of a finite string-rewriting system on a given congruence class,Journal of Computer and System Sciences 35 (1987), 285–310.

    Google Scholar 

17. F. Otto, Completing a finite special string-rewriting system on the congruence class of the empty word,Applicable Algebra in Engineering, Communication and Computing, to appear.

18. F. Otto, L. Zhang, Decision problems for finite special string-rewriting systems that are confluent on some congruence class,Acta Informatica 28 (1991), 477–510.

    Google Scholar 

Download references