×

Context free normal systems and ETOL systems. (English) Zbl 0507.68051


MSC:

68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cocke, J.; Minsky, M., Universality of Tag systems with P=2, J. Assoc. Comput. Mach., 11, 15-20 (1964) · Zbl 0149.12405
[2] Cook, S. A., The solvability of the derivability problem for one-normal systems, J. assoc. comput. mach., 13, 223-225 (1966) · Zbl 0207.31204
[3] Dassow, J., On the circular closure of languages, Elektron. Informationsverarb. Kybernet., 15, 87-94 (1979) · Zbl 0415.68040
[4] Doucet, P., On the membership question in some Lindenmayer systems, Indag. Math., 34, 45-52 (1972) · Zbl 0242.68051
[5] Ginsburg, S.; Greibach, S. A.; Harrison, M. A., One-way stack automata, J. Assoc. Comput. Mach., 14, 389-418 (1967) · Zbl 0171.14803
[6] Greibach, S. A., Chains of full AFL’s, Math. Systems Theory, 4, 231-242 (1970) · Zbl 0203.30102
[7] Herman, G. T., Closure properties of some families of languages associated with biological systems, Inform. and Control, 24, 101-121 (1974) · Zbl 0275.68018
[8] Karhumaki, J., On length sets of informationless L systems, (Lindenmayer, A.; Rozenberg, G., Automata, Languages and Development (1976), North-Holland: North-Holland Amsterdam), 227-242
[9] Kudlek, M., Context Free Normal Systems, (Lecture Notes in Computer Science, Vol. 74 (1979), Springer-Verlag: Springer-Verlag New York/Berlin), 346-352 · Zbl 0408.68066
[10] Van Leeuwen, J., A forgotten connection between Tag-systems and parallel-rewriting, SIGACT News, 6, 4, 19-20 (1974)
[11] Maslov, A. N., On cyclic permutations of languages, Problems Inform. Transmission, 9, 81-87 (1973), (in Russian) · Zbl 0314.68030
[12] Ogden, W. F., Intercalation theorems for pushdown store and stack languages, (Proceedings of the First ACM Symposium on Theory of Computing, (1969)), 31-42 · Zbl 1282.68156
[13] Post, E. L., Formal reduction of the general combinatorial decision problem, Amer. J. Math., 65, 197-215 (1943) · Zbl 0063.06327
[14] Rozenberg, G.; Salomaa, A., The Mathematical Theory of \(L\) Systems (1980), Academic Press: Academic Press London/New York · Zbl 0365.68072
[15] Ruohonen, K., On circular words and \((ω^∗ + ω)\)-powers of words, Elektron. Informationsverarb. Kybernet., 13, 3-12 (1977) · Zbl 0365.68081
[16] Skyum, S., Decomposition theorems for various kinds of languages parallel in nature, SIAM J. Comput., 5, 284-296 (1976) · Zbl 0332.68058
[17] Wang, H., Tag systems and Lag systems, Math. Ann., 152, 65-74 (1963) · Zbl 0131.24602
[18] Hopcropt, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0426.68001
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.