This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
J. Berstel, Congruences plus que parfaites et langages algébrique, Séminaire d'Informatique Théorique (1976–77), Institut de Programmation, 123–147.
R. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach. 29 (1982), 171–182.
R. Book, When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci. 18 (1982), to appear.
R. Book, M. Jantzen, and C. Wrathall, Monadic Thue systems, Theoret. Comput. Sci. 19 (1982), to appear.
R. Book and C. Ó'Dúnlaing, Testing for the Church-Rosser property, Theoret. Comput. Sci. 16 (1981), 223–229.
Y. Cochet, Sur l'algébricité des classes de certaines congruences definies sur le monoide libre, Thèse 3e cycle, Rennes, 1971.
Y. Cochet and M. Nivat, Une generalization des ensembles de Dyck, Israel J. Math. 9 (1971), 389–395.
J. Hopcroft and J. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, 1969.
G. Huet, Confluent reductions: abstract properties and applications to term-rewriting systems, J. Assoc. Comput. Mach. 27 (1980), 797–821.
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.
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.
M. Jantzen, On a special monoid with a single defining relation, Theoret. Comput. Sci 16 (1981), 61–73.
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.
G. Lallement, Semigroups and Combinatorial Applications, Wiley-Interscience, 1979.
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.
M. Nivat, On some families of languages related to the Dyck languages, Proc. 2nd ACM Symp. Theory of Computing (1970), 221–225.
M. Nivat (avec M. Benois), Congruences parfaites et quasi-parfaites, Seminaire Dubreil, 25e Année (1971–72), 7–01–7–09.
M. O'Donnell, Computing in Systems Described by Equations, Lecture Notes in Computer Science 58 (1977), Springer-Verlag.
C. Ó'Dúnlaing, Finite and Infinite Regular Thue Systems, Ph.D. dissertation, University of California at Santa Barbara, 1981.
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.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1982 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Book, R.V. (1982). The power of the Church-Rosser property for string rewriting systems. In: Loveland, D.W. (eds) 6th Conference on Automated Deduction. CADE 1982. Lecture Notes in Computer Science, vol 138. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0000070
Download citation
DOI: https://doi.org/10.1007/BFb0000070
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11558-8
Online ISBN: 978-3-540-39240-8
eBook Packages: Springer Book Archive