×

Nondeterministic semantics of compound diagrams. (English) Zbl 1338.18021

The paper gives a unified description of flow control by using Schmidt’s notion of relational diagram. It is shown how that can be used for giving definitions for a class of programming constructs. It contains several definitions and only two mathematical results that come without proof. The English of the paper is also quite poor.

MSC:

18C10 Theories (e.g., algebraic theories), structure, and semantics
18C50 Categorical semantics of formal languages
68Q55 Semantics in the theory of computing
68Q65 Abstract data types; algebraic specification
03B70 Logic in computer science
06B35 Continuous lattices and posets, applications
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C. Aarts, <em>A Relational Theory of Datatypes</em>,, Department of Computing Science (1992)
[2] R. J. R. Back, On the correctness of refinement in program development,, Thesis (1978)
[3] R. J. R. Back, Combining angels, demons and miracles in program specifications,, Theoretical Computer Science, 100, 365 (1992) · Zbl 0754.68078
[4] R. J. R. Back, A continuous semantics for unbounded nondeterminism,, Theoretical Computer Science, 23, 187 (1983) · Zbl 0498.68005
[5] R. C. Backhouse, <em>Mathematical Induction Made Calculational</em>,, Computing Science Note 94/16 (1994)
[6] R. C. Backhouse, Demonic operators and monotype factors,, Mathematical Structures in Computer Science, 3, 417 (1993) · Zbl 0797.68114
[7] R. Berghammer, <em>Relational Specification of Data Types and Programs</em>, Technical report 9109,, Fakultät für Informatik (1991)
[8] R. Berghammer, Relational specifications,, in Algebraic Logic, 167 (1993) · Zbl 0791.68104
[9] R. Berghammer, Relational algebraic semantics of deterministic and nondeterministic programs,, Theoretical Computer Science, 43, 123 (1986) · Zbl 0596.68019
[10] J. Bharat, Compositional semantics for diagrams using constrained objects,, in International Conference No 2, 94 (2317) · Zbl 1049.68689
[11] C. Böhm, On a family of Turing machines and the related programming languages,, ICC Bull., 3, 185 (1964)
[12] N. Boudriga, On the lattice of specifications: Applications to a specification methodology,, Formal Aspects of Computing, 4, 544 (1992) · Zbl 0782.68077
[13] C. Brink, <em>Relational Methods in Computer Science</em>,, Springer (1997) · Zbl 0871.00027
[14] L. H. Chin, Distributive and modular laws in the arithmetic of relation algebras,, University of California Publications, 1, 341 (1951) · Zbl 0045.31701
[15] B. A. Davey, <em>Introduction to Lattices and Order</em>,, Cambridge Mathematical Textbooks (1990) · Zbl 0701.06001
[16] W. P. De Roever, <em>Recursive Program Schemes: Semantics and Proof Theory</em>,, Math. Centrum Tracts (1974) · Zbl 0344.68001
[17] J. Desharnais, Kleene under a modal demonic star,, Journal of Logic and Algebraic Programming, 66, 127 (2006) · Zbl 1086.68080
[18] J. Desharnais, Kleene under a demonic star,, in 8th International Conference on Algebraic Methodology And Software Technology (AMAST 2000), 355 (2000) · Zbl 0983.68039
[19] J. Desharnais, Embedding a demonic semilattice in a relation algebra,, Theoretical Computer Science, 149, 333 (1995) · Zbl 0874.68199
[20] J. Desharnais, <em>Demonic Relational Semantics of Sequential Programs</em>,, Rapport de recherche DIUL-RR-9406 (1994)
[21] J. Desharnais, A Relational division operator: The conjugate kernel,, Theoretical Comput. Sci., 114, 247 (1993) · Zbl 0779.68058
[22] J. Desharnais, <em>Abstract Relational Semantics</em>,, Ph D. thesis (1989)
[23] E. W. Dijkstra, <em>A Discipline of Programming</em>,, Prentice-Hall (1976) · Zbl 0368.68005
[24] H. Doornbos, Reductivity,, Science of Computer Programming, 26, 217 (1996) · Zbl 0848.68054
[25] H. Doornbos, A relational model of programs without the restriction to Egli-Milner monotone constructs,, in IFIP Transactions, 363 (1994)
[26] H. Doornbos, A calculational approach to mathematical induction,, Theoretical Computer Science, 179, 103 (1997) · Zbl 0901.68124
[27] R. W. Floyd, Assigning meanings to programs,, Proceedings AMS Symposium in Applied Mathematics, 19, 19 (1967) · Zbl 0189.50204
[28] M. Frappier, <em>A Relational Basis for Program Construction by Parts</em>,, Dept. of Computer Science (1994)
[29] C. Gunter, <em>Semantics of Programming Languages,</em>, MIT Press (1992) · Zbl 0823.68059
[30] H. Riis Nielson, <em>Semantics with Applications: An Appetizer</em>, Undergraduate Topics in Computer Science,, Springer-Verlag New York (2007) · Zbl 1126.68052
[31] C. A. R. Hoare, The weakest prespecification, Part I,, Fundamenta Informaticae IX, 9, 51 (1986) · Zbl 0603.68009
[32] C. A. R. Hoare, The weakest prespecification, Part II,, Fundamenta Informaticae IX, 9, 217 (1986) · Zbl 0627.68011
[33] C. A. R. Hoare, Laws of programming,, Communications of the ACM, 30, 672 (1987) · Zbl 0629.68006
[34] Y. I. Ianov, On the equivalence and transformation of program schemes,, Dokl. Akad. Nauk, 1, 8 (1958) · Zbl 0081.34604
[35] J. S. Reich, <em>Relational Denotational Semantics of the While Language</em>,, Department of Computer Science
[36] R. D. Maddux, Relation-algebraic semantics,, Theoretical Computer Science, 160, 1 (1996) · Zbl 0872.68106
[37] A. Mili, A relational approach to the design of deterministic programs,, Acta Informatica, 20, 315 (1983) · Zbl 0508.68003
[38] A. Mili, Relational heuristics for the design of deterministic programs,, Acta Informatica, 24, 239 (1987) · Zbl 0595.68018
[39] D. L. Parnas, A generalized control structure and its formal definition,, Communications of the ACM, 26, 572 (1983) · Zbl 0517.68024
[40] J. Riguet, Programmation et théorie des catégories,, in Proc. ICC Symp. Symbolic Languages in Data Processing, 83 (1962) · Zbl 0143.39901
[41] G. Schmidt, Programs as partial graphs I: Flow equivalence and correctness,, Theoretical Computer Science, 15, 1 (1981) · Zbl 0493.68015
[42] G. Schmidt, <em>Relations and Graphs</em>,, EATCS Monographs in Computer Science (1993)
[43] E. Sekerinski, A calculus for predicative programming,, in Second International Conf. on the Mathematics of Program Construction, 302 (1992) · Zbl 0789.68098
[44] A. Tarski, A lattice-theoretical fixpoint theorem and its applications,, Pacific Journal of Mathematics, 5, 285 (1955) · Zbl 0064.26004
[45] A. Tarski, On the calculus of relations,, J. Symbolic Logic, 6, 73 (1941) · Zbl 0026.24401
[46] F. Tchier, A generalisation of a theorem of Mills,, in Proceedings of the Tenth International Symposium on Computer and Information Sciences, 27 (1995)
[47] F. Tchier, <em>Sémantiques Relationnelles Démoniaques et Vérification de Boucles Non Déterministes</em>,, Ph. D. thesis (1996)
[48] F. Tchier, Applying a generalization of a theorem of Mills to generalized looping structures,, in Science and Engineering in Software Development. A recognition of Harlan D. Mills’ Legacy, 31 (1999)
[49] F. Tchier, La sémantique démoniaque relationnelle des diagrammes composés,, in Proc. 5th Seminar on Relational Methods in computer Science (RelMICS’5) (2000)
[50] F. Tchier, While loop demonic relational semantics monotype/residual style,, 2003 International Conference on Software Engineering Research and Practice (SERP’03) (2003)
[51] F. Tchier, Demonic Semantics: Using monotypes and residuals,, International Journal of Mathematics and Mathematical Sciences, 3, 135 (2004) · Zbl 1066.18006
[52] F. Tchier, Nondeterministic programming theorem,, WSEAS Trans, 5, 1035 (2006)
[53] F. Tchier, <em>From Operational to Denotational Demonic Semantics of Nondeterministic While Loops,</em>, 10th WSEAS International Conference on Communications and Computers (2006)
[54] F. Tchier, Demonic fixed points,, Acta Cybernitica Journal, 17, 533 (2006) · Zbl 1100.68060
[55] F. Tchier, Demonic semantics are equal,, in The 2008 International Conference on Foundations of Computer Science (FCS’08) (2008) · Zbl 1157.68047
[56] M. Walicki, Algebraic approches to nondeterminism: An overview,, ACM Computing Surveys, 29, 30 (1997)
[57] N. T. E. Ward, <em>A refinement Calculus for Nondeterministic Expressions</em>,, Ph.D thesis (1994)
[58] L. Xu, Relational semantics for locally nondeterministic programs,, New Generation Computing, 15, 339 (1997)
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.