Context-free grammars on trees. (English) Zbl 1282.68151

Proceedings of the 1st annual ACM symposium on theory of computing, STOC’69, Marina del Rey, CA, USA, May 5–7, 1969. New York, NY: Association for Computing Machinery (ACM). 143-148 (1969).


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


[1] Aho, A. V., Indexed grammars—an extension of context-free grammars. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1967).
[2] Bar-Hillel, Y., M. Perles and E. Shamir, On formal properties of simple phrase structure grammars. Z. Phonetik Sprachwiss. Kommunikat 14 (1961), 143-172. · Zbl 0106.34501
[3] Fischer, M., Grammars with macro-like productions. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1968).
[4] Knuth, D., Semantics of context-free languages. Math. Systems Theory, vol. 2, no. 2 (June, 1968), pp. 127-158. · Zbl 0169.01401
[5] Petrone, L., Syntax-directed mappings of context-free languages. IEEE Conf. Record, Symp. on Switching and Automata Theory (Oct., 1968).
[6] Thatcher, J. W. and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory, vol. 2, no. 1 (March, 1968), pp. 57-81. · Zbl 0157.02201
[7] Thatcher, J. W., Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comp. Sys. Sci., vol. 1, no. 4 (Dec., 1967), pp. 317-322. · Zbl 0155.01802
[8] Rounds, W. C., Trees, transducers, and transformations. Ph.D. thesis, Stanford Univ., 1968.
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.