NTS grammars and Church-Rosser systems. (English) Zbl 0476.68053


68Q45 Formal languages and automata
03D03 Thue and Post systems, etc.


Zbl 0455.68041
Full Text: DOI


[1] Berstel, J., Congruences plus que parfaites et langages algébrique, (), 123-147
[2] Boasson, L., Derivations et reductions dans LES grammaires algébriques, (), 109-118 · Zbl 0455.68041
[3] R. Book, Confluent and other types of Thue systems, J. Assoc. Comput. Mach., to appear. · Zbl 0478.68032
[4] Book, R.; Jantzen, M.; Wrathall, C., Monadic thue systems, Theoret. comput. sci., 19, (1982), to appear · Zbl 0488.03020
[5] Book, R.; O’Dunlaing, C., Testing for the church-rosser property, Theoret. comput. sci., 16, (1981), to appear · Zbl 0479.68035
[6] Cochet, Y., Sur l’algébricité des classes de certaines congruences définies sur le monoide libre, Thèse 3ème cycle, (1971), Rennes
[7] Cochet, Y.; Nivat, M., Une généralization des ensembles de Dyck, Israel J. math., 9, 389-395, (1971) · Zbl 0215.56005
[8] Frougny, C., Une famille de langages algébriques. congruentiels: LES langages à nonterminaux separés, ()
[9] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, 18th IEEE symposium on the foundations of computer science, J. assoc. comput. Mach., 27, 797-821, (1980) · Zbl 0458.68007
[10] Newman, M.H.A., On theories with a combinatorial definition of ‘equivalence’, Ann. of math., 43, 223-243, (1942) · Zbl 0060.12501
[11] Nivat, M.; Benois, M., Congruences parfaites et quasi-parfaites, Seminaire dubreil, (1971-72), 7-01-09. · Zbl 0338.02018
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.