×

Monadic Thue systems. (English) Zbl 0488.03020


MSC:

03D03 Thue and Post systems, etc.
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A., Pattern matching in strings, (Book, R., Formal Language Theory: Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 325-347
[2] Autebert, J.-M.; Boasson, L., Generators of cones and cylinders, (Book, R., Formal Language Theory: Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 49-87
[3] Bar-Hillel, Y.; Perles, M.; Shamir, E., On formal properties of simple phrase structure grammars, Z. Phonetik, Sprachwissenschaft, und Kommunikationsforschung. (Bar-Hillel, Y., Language and Information (1964), Addison-Wesley: Addison-Wesley Reading, MA), 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.; 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, (Seminaire d’Informatique Théorique (1976-1977), Institut de Programmation), 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. 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, (Book, R., Formal Language Theory: Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 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.; 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 · Zbl 0338.02018
[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. 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.