×

zbMATH — the first resource for mathematics

Monadic Thue systems. (English) Zbl 0488.03020

MSC:
03D03 Thue and Post systems, etc.
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A., Pattern matching in strings, (), 325-347
[2] Autebert, J.-M.; Boasson, L., Generators of cones and cylinders, (), 49-87
[3] Bar-Hillel, Y.; Perles, M.; Shamir, E., On formal properties of simple phrase structure grammars, (), 14, 143-172, (1961), Chapter 9 · Zbl 0106.34501
[4] M. Benois and Y. Cochet, Congruences quasi-parfaites sur le monoide libre: algébre et combinatorie, manuscript.
[5] Berstel, J., Congruences plus que parfaites et langages algébriques, (), 123-147
[6] Book, R., Confluent and other types of thue systems, J. ACM, 29, 171-182, (1982) · Zbl 0478.68032
[7] Book, R.; O’Dunlaing, C., Testing for the church – rosser property, Theoret. comput. sci., 16, 223-229, (1981) · Zbl 0479.68035
[8] Cochet, Y., Sur l’algébricité des classes de certaines congruences définies sur le monoide libre, Thèse 3^{e} cycle, (1971), Rennes
[9] Cochet, Y.; Nivat, M., Une géneralization des ensembles de Dyck, Israel J. math., 9, 389-395, (1971) · Zbl 0215.56005
[10] Greibach, S., Full AFLs and nested iterated substitution, Information and control, 16, 7-35, (1970) · Zbl 0188.03102
[11] Greibach, S., The hardest context-free language, SIAM J. comput., 2, 304-310, (1973) · Zbl 0278.68073
[12] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, 18th IEEE symposium on foundations of computer science, J. ACM, 27, 797-821, (1980) · Zbl 0458.68007
[13] Huet, G.; Oppen, D., Equations and rewrite rules, (), 349-405
[14] Jantzen, M., On a special monoid with a single defining relation, Theoret. comput. sci., 16, 61-73, (1981) · Zbl 0482.20043
[15] J. Král, A modification of substitution theorem and some necessary and sufficient conditions for sets to be context-free, unpublished manuscript. · Zbl 0199.31301
[16] Newman, M.H.A., On theories with a combinatorial definition of “equivalence”, Ann. math., 43, 223-243, (1942) · Zbl 0060.12501
[17] Nivat, M., On some families of languages related to the Dyck languages, 2nd ACM symposium on theory of computing, 221-225, (1970)
[18] Nivat, M.; Benois, M., Congruences parfaites et quasi-parfaites, Seminaire dubreil, (1971-1972), 7-01-09
[19] Raulefs, P.; Siekmann, J.; Szabo, P.; Unvericht, E., A short survey on the state of the art in matching and unification problems, SIGSAM bull., 13, 14-20, (1979)
[20] Rosen, B., Tree manipulating systems and church-rosser systems, J. ACM, 20, 160-187, (1973) · Zbl 0267.68013
[21] Savitch, W., How to make arbitrary grammars look like context-free grammars, SIAM J. comput., 2, 174-182, (1973) · Zbl 0298.68057
[22] Stanat, D., Formal languages and power series, 3rd ACM symposium on theory of computing, 1-11, (1971) · Zbl 0257.68076
[23] Ullian, J., Partial-algorithm problems for context-free languages, Information and control, 11, 80-101, (1967) · Zbl 0155.34202
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.