×

Program equivalence and context-free grammars. (English) Zbl 0315.68063


MSC:

68Q45 Formal languages and automata
68N01 General topics in the theory of software
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Ullman, J. D., (The Theory of Parsing, Translation, and Compiling, Vol. 2 (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J.)
[2] Ashcroft, E. A.; Manna, Z.; Pnueli, A., Decidable properties of monadic functional schemas, J. Assoc. Comput. Mach., 20, 489-499 (1973) · Zbl 0289.68036
[3] Constable, R. L.; Gries, D., On classes of program schemata, SIAM J. Computing, 1, 66-118 (1972) · Zbl 0247.68031
[4] Downey, P. J., Formal languages and recursion schemes, (Ph.D. Thesis (1974), Harvard University)
[5] Engelfriet, J., Translation of simple program schemes, (Nivat, M., Automata, Languages and Programming (1973), North-Holland: North-Holland Amsterdam), 215-223 · Zbl 0264.68007
[6] Garland, S. J.; Luckham, D. C., Program schemes, recursion schemes, and formal languages, J. Comput. System Sci., 7, 119-160 (1973) · Zbl 0369.68014
[7] Kaplan, D. M., Regular expressions and the equivalence of programs, J. Comput. System Sci., 3, 361-386 (1969) · Zbl 0187.13603
[8] Keller, R. M., A solvable program-schema equivalence problem, (Proceedings of the 5th Annual Princeton Conference on Information Science and Systems (1971)), 301-306
[9] Kildall, G. A., A unified approach to global program optimization, (ACM Symposium on Principles of Programming Languages (1973)), 194-206 · Zbl 0309.68020
[10] Lewis, C. H.; Rosen, B. K., Recursively defined data types, Part 1, (ACM Symposium on Principles of Programming Languages (1973)), 125-138 · Zbl 0334.68024
[11] Luckham, D. C.; Park, D. M.R.; Paterson, M. S., On formalized computer programs, J. Comput. System Sci., 4, 220-249 (1970) · Zbl 0209.18704
[12] Manna, Z.; Ness, S.; Vuillemin, J., Inductive methods for proving properties of programs, Comm. ACM, 16, 491-502 (1973) · Zbl 0278.68019
[13] McCarthy, J., Basis for a mathematical theory of computation, (Braffort, P.; Hirschberg, D., Computer Programming and Formal Systems (1963), North-Holland: North-Holland Amsterdam), 33-70 · Zbl 0203.16402
[14] Paterson, M. S.; Hewitt, C. E., Comparative schematalogy, (Proceedings of the ACM Conf. on Concurrent Systems and Parallel Computation (1970)), 119-127
[15] Rosen, B. K., Tree-manipulating systems and Church-Rosser theorems, J. Assoc. Comput. Mach., 20, 160-187 (1973) · Zbl 0267.68013
[16] Rosenkrantz, D. J.; Stearns, R. E., Properties of deterministic top-down grammars, Inform. Contr., 17, 226-256 (1970) · Zbl 0209.02703
[17] Rounds, W. C., Tree-oriented proofs of some theorems on context-free and indexed languages, (Second Annual ACM Symposium on Theory of Computing (1970)), 109-116
[18] Scott, D., Outline of a mathematical theory of computation, (Proceedings of the 4th annual Princeton Conference on Information Science and Systems (1970)), 169-176
[19] Strong, H. R., High level languages of maximum power, (Proceedings of the 12th Annual IEEE Symposium on Switching and Automata Theory (1971)), 1-4
[20] Strong, H. R., Translating recursion equations into flow charts, J. Comput. System Sci., 5, 254-285 (1951) · Zbl 0239.68002
[21] Vuillemin, J., Correct and optimal implementations of recursion in a simple programming language, (Proceedings of the 5th Annual ACM Symposium on Theory of Computing (1973)), 224-239 · Zbl 0305.68013
[22] Walker, S. A.; Strong, H. R., Characterizations of flowchartable recursions, J. Comput. System Sci., 7, 404-447 (1973) · Zbl 0266.68011
[23] Zeiger, H. P., Formal models for some features of programming languages, (ACM Symposium on Theory of Computing (1969)), 211-215 · Zbl 1282.68090
[24] Rosen, B. K., Program equivalence and context-free grammars, (Proceedings of the 13th Annual IEEE Symposium on Switching and Automata Theory (1972)), 7-18
[25] Courcelle, B.; Vuillemin, J., Semantics and axiomatics of a simple recursive language, (Proceedings of the 6th Annual ACM Symposium on Theory of Computing (1974)), 13-26 · Zbl 0358.68015
[26] Courcelle, B., Recursive schemes, algebraic trees, and deterministic languages, (Proceedings of the 15th Annual IEEE Symposium on Switching and Automata Theory (1974)), 52-62
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.