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, (), 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 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, (), 263-297 · Zbl 0188.04902
[11] Lallemont, G., Semigroups and combinatorial applications, (1979), Wiley New York
[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
[14] O’Donnell, M., Computing in systems described by equations, () · Zbl 0421.68038
[15] O’Dúnlaing, C., Finite and infinite regular thue systems, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.