The power of the Church-Rosser property for string rewriting systems

1. J. Berstel, Congruences plus que parfaites et langages algébrique, Séminaire d'Informatique Théorique (1976–77), Institut de Programmation, 123–147.

   Google Scholar 

2. R. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), 171–182.

   Google Scholar 

3. R. Book, When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci. 18 (1982), to appear.

   Google Scholar 

4. R. Book, M. Jantzen, and C. Wrathall, Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), to appear.

   Google Scholar 

5. R. Book and C. Ó'Dúnlaing, Testing for the Church-Rosser property, Theoret. Comput. Sci. 16 (1981), 223–229.

   Article  Google Scholar 

6. Y. Cochet, Sur l'algébricité des classes de certaines congruences definies sur le monoide libre, Thèse 3^e cycle, Rennes, 1971.

   Google Scholar 

7. Y. Cochet and M. Nivat, Une generalization des ensembles de Dyck, Israel J. Math. 9 (1971), 389–395.

   Google Scholar 

8. J. Hopcroft and J. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969.

   Google Scholar 

9. G. Huet, Confluent reductions: abstract properties and applications to term-rewriting systems, J. Assoc. Comput. Mach. 27 (1980), 797–821.

   Google Scholar 

10. G. Huet and D. Oppen, Equations and rewrite rules: a survey, in R. Book (ed.), Formal Language Theory: Perspectives and Open Problems, Academic Press, 1980, 349–405.

    Google Scholar 

11. H. Hunt, D. Rosenkrantz, and T. Szymanski, On the equivalence, containment, and covering problems for the regular and contextfree languages, J. Comput. Syst. Sci. 12 (1976), 222–268.

    Google Scholar 

12. M. Jantzen, On a special monoid with a single defining relation, Theoret. Comput. Sci 16 (1981), 61–73.

    Article  Google Scholar 

13. D. Knuth and P. Bendix, Simple word problems in universal algebras, in J. Leech (ed.). Computational Problems in Abstract Algebra, Pergamon Press, 1970, 263–297.

    Google Scholar 

14. G. Lallement, Semigroups and Combinatorial Applications, Wiley-Interscience, 1979.

    Google Scholar 

15. A. Meyer and L. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, Proc. 13th IEEE Symp. Switching and Automata Theory (1972), 125–129.

    Google Scholar 

16. M. Nivat, On some families of languages related to the Dyck languages, Proc. 2nd ACM Symp. Theory of Computing (1970), 221–225.

    Google Scholar 

17. M. Nivat (avec M. Benois), Congruences parfaites et quasi-parfaites, Seminaire Dubreil, 25^e Année (1971–72), 7–01–7–09.

    Google Scholar 

18. M. O'Donnell, Computing in Systems Described by Equations, Lecture Notes in Computer Science 58 (1977), Springer-Verlag.

    Google Scholar 

19. C. Ó'Dúnlaing, Finite and Infinite Regular Thue Systems, Ph.D. dissertation, University of California at Santa Barbara, 1981.

    Google Scholar 

20. P. Raulefs, J. Siekmann, P. Szabo, and E. Unvericht, A short survey of the state of the art in matching and unification problems, SIGSAM Bulletin 13 (1979), 14–20.

    Google Scholar 

Download references