Decidable sentences of Church-Rosser congruences. (English) Zbl 0525.68015


68Q65 Abstract data types; algebraic specification
03D03 Thue and Post systems, etc.
20M35 Semigroups in automata theory, linguistics, etc.
03B25 Decidability of theories and sets of sentences
Full Text: DOI


[1] Berstel, J., Congruences plus que parfaites et langages algébrique, (Séminaire d’Informatique Théorique (1976-77), Institut de Programmation), 123-147
[2] Book, R., Confluent and other types of Thue systems, J. Assoc. Comput. Mach., 29, 171-182 (1982) · Zbl 0478.68032
[3] Book, R., When is a monoid a group? The Church-Rosser case is tractable, Theoret. Comput. Sci., 18, 325-331 (1982) · Zbl 0489.68021
[4] Book, R.; Jantzen, M.; Wrathall, C., Monadic Thue systems, Theoret. Comput. Sci., 19, 231-251 (1982) · Zbl 0488.03020
[5] Book, R.; Ó’Dúnlaing, C., Testing for the Church-Rosser property, Theoret. Comput. Sci., 16, 223-229 (1981) · Zbl 0479.68035
[6] Cochet, Y.; Nivat, M., Une généralisation des ensembles de Dyck, Israel J. Math., 9, 389-395 (1971) · Zbl 0215.56005
[7] Hopcroft, J.; Ullman, J., Formal Languages and Their Relation to Automata (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[8] Huet, G., Confluent reductions: Abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach., 27, 797-821 (1980) · Zbl 0458.68007
[9] Hunt, H.; Rosenkrantz, D.; Szymanski, T., On the equivalence, containment, and covering problems for the regular and context-free languages, J. Comput. Systems Sci., 12, 222-268 (1976) · Zbl 0334.68044
[10] Knuth, D.; Bendix, P., Simple word problems in universal algebras, (Leech, J., Computational Problems and Abstract Algebra (1920), Pergamon Press: Pergamon Press Oxford), 263-297 · Zbl 0188.04902
[11] Lallemont, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[12] Meyer, A.; Stockmeyer, L., The equivalence problem for regular expressions with squaring requires exponential space, Proc. 13th IEEE Symp. Switching and Automata Theory, 125-129 (1972)
[13] Nivat (avec M. Benois), M., Congruences parfaites et quasi-parfaites, Séminaire Dubreil 25e Année (1971-1972), 7-01-09 · Zbl 0338.02018
[14] O’Donnell, M., Computing in Systems Described by Equations, (Lecture Notes in Computer Science, 58 (1977), Springer: Springer Berlin) · Zbl 0421.68038
[15] O’Dúnlaing, C., Finite and infinite regular Thue systems, (Ph.D. Dissertation (1981), University of California at Santa Barbara) · Zbl 0512.03018
[16] Rosen, B., Tree-manipulating systems and Church-Rosser theorems, J. Assoc. Comput. Mach., 20, 160-187 (1973) · Zbl 0267.68013
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.