Completeness results for the equivalence of recursive schemas. (English) Zbl 0342.68008


68Q45 Formal languages and automata
68N01 General topics in the theory of software
03D99 Computability and recursion theory


Full Text: DOI


[1] Ashcroft, E. A.; Manna, Z.; Pnueli, A., Decidable properties of monadic functional schemas, (Kohavi, Z.; Paz, A., Theory of Machines and Computations (1971), Academic Press: Academic Press New York), 3-18 · Zbl 0306.68048
[2] deBakker, J. W., Recursive procedures, Math. Center Tracts No. 24, Amsterdam (1971) · Zbl 0274.02015
[3] deBakker, J. W.; deRoever, W. P., A calculus for recursive program schemes, (Proceedings of the IRIA Colloquium (1972), North-Holland: North-Holland Amsterdam) · Zbl 0238.68006
[4] deBakker, J. W.; Scott, D., A theory of programs (1969), unpublished
[5] Courcelle, B., Recursive schemes, algebraic trees, deterministic languages, (Proceedings of the 15th SWAT Symposium (1974))
[6] Courcelle, B., Grammaires canoniques des langages simples déterministes, RAIRO, No. 1, Paris (1974)
[7] Courcelle, B.; Kahn, G.; Vuillemin, J., Algorithmes d’équivalence pour des équations récursives simples, (Rapport Laboria No. 37 (1973), IRIA) · Zbl 0285.68022
[8] Nivat, M.; Vuillemin, J., Algebraic interpretations for recursive programs, (Rapport Laboria (1975), IRIA)
[9] Courcelle, B.; Vuillemin, J., Complétude d’un système formel pour l’équivalence de schèmas récursifs monadiques, (Comptes-Rendu du Collogue de Paris. Comptes-Rendu du Collogue de Paris, Institut de Programmation (April 1974)) · Zbl 0302.68095
[10] Gordon, M., Evaluation and denotation of pure LISP programs: A worked example in semantics, Thesis, Edinburgh (1973)
[11] Paterson, M. S.; Hewitt, C., Comparative Schematology, (Record of Project MAC Conference on Parallel Computation (1970), ACM: ACM New York) · Zbl 0401.68002
[12] Hitchcock, P.; Park, D., Induction rules and proofs of termination, (Proceedings of the IRIA Colloquium (1972), North-Holland: North-Holland Amsterdam) · Zbl 0387.68011
[13] Hopcroft, J. E.; Korenjak, A. J., Simple deterministic languages, (Proceedings of the Seventh SWAT Symposium (1966)), 36-46 · Zbl 0313.68061
[14] Ianov, Y. I., The logical schemes of algorithms, (Problems in Cybernetics, Vol. 1 (1960), Pergamon Press: Pergamon Press Elmsford, N.Y.)
[15] Kahn, G., A preliminary theory of parallel programs, (Rapport Laboria No. 6 (1973), IRIA)
[16] Luckham, D.; Park, D.; Paterson, M. S., On formalized computer programs, J. Comput. System Sci., 4, 220-249 (1970) · Zbl 0209.18704
[17] Manna, Z.; Ness, S.; Vuillemin, J., Inductive methods for proving properties of programs, Commun. ACM, 16 (1973) · Zbl 0278.68019
[18] Milner, R., (Models of LCF, AIM-186/CS-332 (1973), Stanford University) · Zbl 0364.02018
[19] Milner, R., Processes: A model of computing agents, ((1973), University of Edinburgh Memorandum) · Zbl 0316.68017
[20] Milner, R.; Weyrauch, R., Proving Compiler Correctness in a Mechanized Logic, (Machine Intelligence, 7 (1972), Edinburgh University Press) · Zbl 0259.68008
[21] Nivat, M., On the Interpretation of Polyadic Recursive Schemes, (Rapport Laboria (1974), IRIA) · Zbl 0346.68041
[22] Paterson, M., Program Schemata, (Machine Intelligence 3 (1968), Edinburgh University Press) · Zbl 0198.32603
[23] Plotkin, G., (LCF Considered as a Programming Language (1974), School of Artificial Intelligence, University of Edinburgh Memorandum) · Zbl 0369.68006
[24] deRoever, W. P., Operational, mathematical and axiomatized semantics for recursive procedures and data structures, Mathematisch Centrum Report, Amsterdam (1974)
[25] Rosen, B., Program equivalence and context-free grammars (1974), IBM Research Memo: IBM Research Memo Yorktown Heights, N.Y.
[26] Scott, D., Outline of a mathematical theory of computation, (Oxford Monograph PRG-2 (1970), Oxford University) · Zbl 0419.68076
[27] Scott, D., Continuous lattices, (Oxford Monograph PRG-7 (1972), Oxford University) · Zbl 0239.54006
[28] Scott, D.; Strachey, C., Towards a mathematical semantics for computer languages, (Oxford Monograph PRG-6 (1972), Oxford University) · Zbl 0268.68004
[29] Vuillemin, J., Proof techniques for recursive programs, (Ph.D. Thesis (1973), Stanford University)
[30] Vuillemin, J., Syntaxe, sémantique et axiomatique d’un langage de programmation simple, (Thèse d’État (1974), Université de Paris VII) · Zbl 0327.68006
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.