Formal computations of non deterministic recursive program schemes. (English) Zbl 0441.68044


68W30 Symbolic computation and algebraic computation
68Q60 Specification and verification (program logics, model checking, etc.)
Full Text: DOI


[1] A. Arnold. Systèmes d’équations dans le magmoide. Ensembles rationnels et algébriques d’arbres. Thèse d’Etat, Université de Lille I (1977).
[2] A. Arnold and M. Dauchet. Théorie des magmoides. Publications du Laboratoire de Calcul, HS-77, Université de Lille I (1977). · Zbl 0443.68053
[3] A. Arnold and M. Nivat. Nondeterministic recursive program schemes, in ”Fundamentals of Computation Theory 77” (M. Karpinski, ed.) Lecture Notes in Computer Science no. 56, Springer-Verlag (1977) 12–21.
[4] A. Arnold and M. Nivat. The metric space of infinite trees. Algebraic and topological properties. Rapport IRIA-Laboratoria no. 323 (1978).
[5] J. W. de Bakker. Semantics and termination of nondeterministic recursive programs, in ”Automata, Languages and Programming” 3rd Colloquium, Edinburgh 1976 (S. Michaelson and R. Milner, eds) Edinburgh University Press (1976). · Zbl 0354.68021
[6] A. Blikle. Proving programs by sets of computations, in ”Mathematical Foundations of Computer Science”, 3rd Colloquium, Jadwisin, 1974 (A. Blikle, ed.), Lecture Notes in Computer Science no. 28, Springer-Verlag (1974) 333–358.
[7] G. Boudol. Langages polyadiques algébriques. Théorie des schémas de programme: sémantique de l’appel par valeur. Thèse 3ème cycle, Université de Paris VII (1975).
[8] B. Courcelle and M. Nivat. Algebraic families of interpretations, 17th IEEE Symp. On Foundations of Computer Science, Houston (1976) 137–146.
[9] P. J. Downey. Formal languages and recursion schemes. Ph.D. Dissertation, Harvard University (1974).
[10] H. Egli. A mathematical model for nondeterministic computations. Unpublished report, Zürich (1975). · Zbl 0359.68017
[11] J. Engelfriet and E. M. Schmidt. IO and OI.J. Comput. System Sci. 15 (1977) 328–353 and 16 (1978) 67–99. · Zbl 0366.68053
[12] M. J. Fischer. Grammars with macro-like productions. 9th IEEE Symposium on Switching and automata theory (1968) 131–142.
[13] R. N. Floyd. Nondeterministic algorithms.J. Assoc. Comput. Mach. 14 (1967) 636–644. · Zbl 0153.47006
[14] J. H. Gallier. Semantics and correctness of nondeterministic flowchart programs with recursive procedures,in, ”Automata, Languages and Programming” 5th colloquium, Udine, 1978 (G. Ausiello and C. Böhm, eds) Lecture Notes in Computer Science no. 62, Springer-Verlag (1978) 251–267.
[15] D. Harel and V. R. Pratt. Nondeterminism in logics of programs,in Proc. of the 5th ACM Symposium on Principles of programming languages, Tucson (1978).
[16] M. Hennessy and E. A. Ashcroft. The semantics of nondeterminism,in ”Automata, Languages and Programming— 3rd colloquium, Edinburgh, 1976 (S. Michaelson and R. Milner, eds) Edinburgh University Press (1976) 478–493. · Zbl 0379.02015
[17] Z. Manna. The Correctness of nondeterministic programs.Artificial Intelligence 1 (1970) 1–26. · Zbl 0203.49402
[18] A. Mazurkiewicz. Proving properties of processes. CC. PAS Report 134, Warszawa (1973). · Zbl 0273.68040
[19] M. Nivat. On the interpretation of polyadic recursive program schemes.Symp. Mathematica 15 (1975) 255–281. · Zbl 0346.68041
[20] M. Nivat. Mots infinis engendrés par une grammaire algébrique.RAIRO Informatique Théorique 11 (1977) 311–327. · Zbl 0371.68025
[21] M. Nivat and A. Arnold. Interprétations métriques de schémas de programmes,in 1{\(\deg\)} Colloque AFCET-SMF de Mathématiques appliquées, Paris 1978, Tome 1 pp. 191–208.
[22] D. Park. Fixpoint induction and proofs of program properties,in ”Machine Intelligence”5 (B. Meltzer and D. Michie, eds), Edinburgh University Press (1969) 59–78. · Zbl 0219.68007
[23] G. D. Plotkin. A powerdomain construction.SIAM J. on Computing 5 (1976) 452–486. · Zbl 0355.68015
[24] W. P. de Roever. On backtracking and greatest fixpoints,in ”Automata, Languages and Programming” 4th Colloquium, Turku, 1977 (A. Salomaa and M. Steinby, eds.), Lecture Notes in Computer Science no. 52, Springer-Verlag (1977) 412–429.
[25] D. Scott. Outline of a mathematical theory of computation. Oxford Research Group Programming, Memo no. RCP2 (1972).
[26] M. B. Smyth. Powerdomains.J. Comput. System. Sci. 16 (1978) 23–36. · Zbl 0391.68011
[27] J. Tiuryn. Continuity problems in the powerset algebra of infinite trees,in ”Les Arbres en Algèbre et en Programmation” 4th Colloquium, Lille (1979) 241–260.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.