A representation of trees by languages. II. (English) Zbl 0428.68088


68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q60 Specification and verification (program logics, model checking, etc.)


Zbl 0377.68040
Full Text: DOI


[1] Arnold, A.; Dauchet, M., Un théoréme de duplication pour les forêts algébriques, J. Comput. System Sci., 13, 223-244 (1976) · Zbl 0335.68050
[2] Arnold, A.; Dauchet, M., Forêts algébriques et homomorphismes inverses, (Rep. No. 55 (1975), Laboratoire de Calcul de l’Université de Lille) · Zbl 0395.68073
[3] Boudol, G., Langages polyadiques algébriques, (Thèse de 3ème cycle (1976), Université de Paris-7)
[4] Courcelle, B., Une forme canonique pour les grammaires simples déterministes, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge, 19-36 (1974) · Zbl 0285.68033
[5] Courcelle, B., Recursive schemes, algebraic trees and deterministic languages, Proc. 15th Annual Symp. on Switching and Automata Theory, 52-62 (1974), New Orleans
[6] Courcelle, B., Sur les ensembles algébriques d’arbres et les langages déterministes, quelques applications à la théorie des schémas de programmes, (Thèse (1976), Université de Paris-7)
[7] B. Courcelle, On jump-deterministic pushdown automata, Math. Systems Theory; B. Courcelle, On jump-deterministic pushdown automata, Math. Systems Theory · Zbl 0365.02021
[8] Courcelle, B.; Nivat, M., Algebraic families of interpretations, 17th Annual Symp. on F.O.C.S. (1976), Houston
[9] Courcelle, B.; Vuillemin, J., Completeness results for the equivalence of recursive schemas, J. Comput. System Sci., 12, 179-197 (1976) · Zbl 0342.68008
[10] Doner, J. E., Tree acceptors and some of their applications, J. Comput. System Sci., 4, 406-451 (1970) · Zbl 0212.02901
[11] Engelfriet, J., Bottom-up and top-down tree transformations — a comparison, Math. Systems Theory, 9, 199-231 (1975) · Zbl 0335.68061
[12] J. Engelfriet and E.M. Schmidt, IO and OI, J. Comput. System Sci.; J. Engelfriet and E.M. Schmidt, IO and OI, J. Comput. System Sci.
[13] Fischer, M., Grammars with macro-like instructions, Proc. 9th Annual Symp. on Switching and Automata Theory, 131-142 (1968)
[14] Friedman, E., Equivalence problems for deterministic context-free languages and monadic recursion schemes, J. Comput. System Sci., 14, 344-359 (1977) · Zbl 0358.68109
[15] Friedman, E., The inclusion problem for simple languages, Theoret. Comput. Sci., 1, 297-316 (1976) · Zbl 0349.68032
[16] Ginsburg, S., The Mathematical Theory of Context-free Languages (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0184.28401
[17] Goguen, J., Initial algebra semantics, J. Assoc. Comput. Mach., 24, 68-95 (1977) · Zbl 0359.68018
[18] Harrison, M. A.; Havel, I. M., Strict deterministic grammars, J. Comput. System Sci., 7, 237-277 (1973) · Zbl 0261.68036
[19] Harrison, M. A.; Havel, I. M., On the parsing of deterministic languages, J. Assoc. Comput. Mach., 21, 525-548 (1974) · Zbl 0296.68084
[20] N. Honda and M. Oyamaguchi, The decidability of equivalence for deterministic stateless pushdown automata (submitted for publication).; N. Honda and M. Oyamaguchi, The decidability of equivalence for deterministic stateless pushdown automata (submitted for publication). · Zbl 0393.68078
[21] Hopcroft, J. E.; Korenjak, A. J., Simple deterministic languages, Proc. 7th Symposium on Switching and Automata Theory, 36-46 (1966), Berkeley · Zbl 0313.68061
[22] Nivat, M., Eléments de la théorie générale des codes, (Caianie, lo, Automata Theory (1966), Academic Press: Academic Press London), 278-294 · Zbl 0208.45101
[23] Nivat, M., On the Interpretation of Recursive Programs Schemes, (Symposia Mathematica, vol. 15 (1975), Academic Press: Academic Press New York)
[24] Nivat, M., Interprétation universalle d’un schéma de programme recursif, Proc. Int. School on Theory and Applications of Computers (1976), Erice
[25] Rosen, B., Tree-manipulating systems and Church-Rosser Theorems, J. Assoc. Comput. Mach., 20, 160-187 (1973) · Zbl 0267.68013
[26] Rosen, B., Program equivalence and context-free grammars, J. Comput. System Sci., 11, 358-374 (1975) · Zbl 0315.68063
[27] Rosenkrantz, D. J.; Stearns, R. E., Properties of deterministic top-down grammars, Information and Control, 17, 226-256 (1970) · Zbl 0209.02703
[28] Rounds, W. C., Tree-oriented proofs of some theorems on context-free and indexed languages, Proc. 2nd ACM Symp. on Computing, 109-116 (1970)
[29] Schützenberger, M. P., On context-free languages and push-down automata, Information and Control, 16, 246-264 (1963) · Zbl 0123.12502
[30] Stearns, R. E., A regularity test for pushdown machines, Information and Control, 11, 323-340 (1967) · Zbl 0155.01901
[31] Thatcher, J., Tree automata: an informal survey, (Aho, A., Currents in the Theory of Computing (1973), Prentice Hall), 143-172
[32] Valiant, L. G., The equivalence problem for deterministic finite turn pushdown automata, Information and Control, 25, 123-133 (1972) · Zbl 0285.68025
[33] Valiant, L. G., Decision procedures for families of deterministic pushdown automata, (Rep. No. 7 (1973), Warwick University) · Zbl 0566.94022
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.