December  2015, 8(6): 1357-1371. doi: 10.3934/dcdss.2015.8.1357

Nondeterministic semantics of compound diagrams

1. 

Mathematics department, King Saud University, P.O.Box 22452, Riyadh 11495, Saudi Arabia

Received  May 2015 Revised  July 2015 Published  December 2015

We presented a unified description of flow control and single steps of a program is given to obtain flexible definitions of algebraic manipulations. This is achieved by using the notion of relational diagram. We show how the notion of relational diagram, introduced by Schmidt, can be used to give a demonic definition for a wide range of programming constructs. It is shown that the input-output relation of a compound diagram is equal to that of the diagram in which each sub-diagram has been replaced by its input-output relation. This process is repeated until elementary diagrams is obtained.
Citation: Fairouz Tchier. Nondeterministic semantics of compound diagrams. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1357-1371. doi: 10.3934/dcdss.2015.8.1357
References:
[1]

C. Aarts, R. Backhouse, P. Hoogendijk, E. Voermans and J. van der Woude, A Relational Theory of Datatypes,, Department of Computing Science, (1992).   Google Scholar

[2]

R. J. R. Back, On the correctness of refinement in program development,, Thesis, (1978).   Google Scholar

[3]

R. J. R. Back, Combining angels, demons and miracles in program specifications,, Theoretical Computer Science, 100 (1992), 365.  doi: 10.1016/0304-3975(92)90309-4.  Google Scholar

[4]

R. J. R. Back, A continuous semantics for unbounded nondeterminism,, Theoretical Computer Science, 23 (1983), 187.  doi: 10.1016/0304-3975(83)90055-5.  Google Scholar

[5]

R. C. Backhouse and H. Doornbos, Mathematical Induction Made Calculational,, Computing Science Note 94/16, (1994).   Google Scholar

[6]

R. C. Backhouse and J. van der Woude, Demonic operators and monotype factors,, Mathematical Structures in Computer Science, 3 (1993), 417.  doi: 10.1017/S096012950000030X.  Google Scholar

[7]

R. Berghammer, Relational Specification of Data Types and Programs, Technical report 9109,, Fakultät für Informatik, (1991).   Google Scholar

[8]

R. Berghammer and G. Schmidt, Relational specifications,, in Algebraic Logic, (1993), 167.   Google Scholar

[9]

R. Berghammer and H. Zierer, Relational algebraic semantics of deterministic and nondeterministic programs,, Theoretical Computer Science, 43 (1986), 123.  doi: 10.1016/0304-3975(86)90172-6.  Google Scholar

[10]

J. Bharat and T. Pallavi, Compositional semantics for diagrams using constrained objects,, in International Conference No 2, (2317), 94.   Google Scholar

[11]

C. Böhm, On a family of Turing machines and the related programming languages,, ICC Bull., 3 (1964), 185.   Google Scholar

[12]

N. Boudriga, F. Elloumi and A. Mili, On the lattice of specifications: Applications to a specification methodology,, Formal Aspects of Computing, 4 (1992), 544.   Google Scholar

[13]

C. Brink, W. Kahl and G. Schmidt, eds., Relational Methods in Computer Science,, Springer, (1997).  doi: 10.1007/978-3-7091-6510-2.  Google Scholar

[14]

L. H. Chin and A. Tarski, Distributive and modular laws in the arithmetic of relation algebras,, University of California Publications, 1 (1951), 341.   Google Scholar

[15]

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order,, Cambridge Mathematical Textbooks, (1990).   Google Scholar

[16]

W. P. De Roever, Recursive Program Schemes: Semantics and Proof Theory,, Math. Centrum Tracts, (1974).   Google Scholar

[17]

J. Desharnais, B. Möller and F. Tchier, Kleene under a modal demonic star,, Journal of Logic and Algebraic Programming, 66 (2006), 127.  doi: 10.1016/j.jlap.2005.04.006.  Google Scholar

[18]

J. Desharnais, B. Möller and F. Tchier, Kleene under a demonic star,, in 8th International Conference on Algebraic Methodology And Software Technology (AMAST 2000), (2000), 355.  doi: 10.1007/3-540-45499-3_26.  Google Scholar

[19]

J. Desharnais, N. Belkhiter, S. B. M. Sghaier, F. Tchier, A. Jaoua, A. Mili and N. Zaguia, Embedding a demonic semilattice in a relation algebra,, Theoretical Computer Science, 149 (1995), 333.  doi: 10.1016/0304-3975(94)00271-J.  Google Scholar

[20]

J. Desharnais, F. Tchier and R. Khédri, Demonic Relational Semantics of Sequential Programs,, Rapport de recherche DIUL-RR-9406, (1994).   Google Scholar

[21]

J. Desharnais, A. Jaoua, F. Mili, N. Boudriga and A. Mili, A Relational division operator: The conjugate kernel,, Theoretical Comput. Sci., 114 (1993), 247.  doi: 10.1016/0304-3975(93)90074-4.  Google Scholar

[22]

J. Desharnais, Abstract Relational Semantics,, Ph D. thesis, (1989).   Google Scholar

[23]

E. W. Dijkstra, A Discipline of Programming,, Prentice-Hall, (1976).   Google Scholar

[24]

H. Doornbos, Reductivity,, Science of Computer Programming, 26 (1996), 217.  doi: 10.1016/0167-6423(95)00027-5.  Google Scholar

[25]

H. Doornbos, A relational model of programs without the restriction to Egli-Milner monotone constructs,, in IFIP Transactions, (1994), 363.   Google Scholar

[26]

H. Doornbos, R. Backhouse and J. van der Woude, A calculational approach to mathematical induction,, Theoretical Computer Science, 179 (1997), 103.  doi: 10.1016/S0304-3975(96)00154-5.  Google Scholar

[27]

R. W. Floyd, Assigning meanings to programs,, Proceedings AMS Symposium in Applied Mathematics, 19 (1967), 19.   Google Scholar

[28]

M. Frappier, A Relational Basis for Program Construction by Parts,, Dept. of Computer Science, (1994).   Google Scholar

[29]

C. Gunter, Semantics of Programming Languages,, MIT Press, (1992).   Google Scholar

[30]

H. Riis Nielson and F. Nielson, Semantics with Applications: An Appetizer, Undergraduate Topics in Computer Science,, Springer-Verlag New York, (2007).   Google Scholar

[31]

C. A. R. Hoare and J. He, The weakest prespecification, Part I,, Fundamenta Informaticae IX, 9 (1986), 51.   Google Scholar

[32]

C. A. R. Hoare and J. He, The weakest prespecification, Part II,, Fundamenta Informaticae IX, 9 (1986), 217.   Google Scholar

[33]

C. A. R. Hoare, et al., Laws of programming,, Communications of the ACM, 30 (1987), 672.  doi: 10.1145/27651.27653.  Google Scholar

[34]

Y. I. Ianov, On the equivalence and transformation of program schemes,, Dokl. Akad. Nauk, 1 (1958), 8.  doi: 10.1145/368924.368930.  Google Scholar

[35]

J. S. Reich and J. L. Jacob, Relational Denotational Semantics of the While Language,, Department of Computer Science, ().   Google Scholar

[36]

R. D. Maddux, Relation-algebraic semantics,, Theoretical Computer Science, 160 (1996), 1.  doi: 10.1016/0304-3975(95)00082-8.  Google Scholar

[37]

A. Mili, A relational approach to the design of deterministic programs,, Acta Informatica, 20 (1983), 315.  doi: 10.1007/BF00264277.  Google Scholar

[38]

A. Mili, J. Desharnais and F. Mili, Relational heuristics for the design of deterministic programs,, Acta Informatica, 24 (1987), 239.  doi: 10.1007/BF00265990.  Google Scholar

[39]

D. L. Parnas, A generalized control structure and its formal definition,, Communications of the ACM, 26 (1983), 572.  doi: 10.1145/358161.358168.  Google Scholar

[40]

J. Riguet, Programmation et théorie des catégories,, in Proc. ICC Symp. Symbolic Languages in Data Processing, (1962), 83.   Google Scholar

[41]

G. Schmidt, Programs as partial graphs I: Flow equivalence and correctness,, Theoretical Computer Science, 15 (1981), 1.  doi: 10.1016/0304-3975(81)90060-8.  Google Scholar

[42]

G. Schmidt and T. Ströhlein, Relations and Graphs,, EATCS Monographs in Computer Science, (1993).  doi: 10.1007/978-3-642-77968-8.  Google Scholar

[43]

E. Sekerinski, A calculus for predicative programming,, in Second International Conf. on the Mathematics of Program Construction, (1992), 302.  doi: 10.1007/3-540-56625-2_20.  Google Scholar

[44]

A. Tarski, A lattice-theoretical fixpoint theorem and its applications,, Pacific Journal of Mathematics, 5 (1955), 285.  doi: 10.2140/pjm.1955.5.285.  Google Scholar

[45]

A. Tarski, On the calculus of relations,, J. Symbolic Logic, 6 (1941), 73.  doi: 10.2307/2268577.  Google Scholar

[46]

F. Tchier and J. Desharnais, A generalisation of a theorem of Mills,, in Proceedings of the Tenth International Symposium on Computer and Information Sciences, (1995), 27.   Google Scholar

[47]

F. Tchier, Sémantiques Relationnelles Démoniaques et Vérification de Boucles Non Déterministes,, Ph. D. thesis, (1996).   Google Scholar

[48]

F. Tchier and J. Desharnais, 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, (1999), 31.  doi: 10.1109/SESD.1999.781109.  Google Scholar

[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).   Google Scholar

[50]

F. Tchier, While loop demonic relational semantics monotype/residual style,, 2003 International Conference on Software Engineering Research and Practice (SERP'03), (2003).   Google Scholar

[51]

F. Tchier, Demonic Semantics: Using monotypes and residuals,, International Journal of Mathematics and Mathematical Sciences, 3 (2004), 135.  doi: 10.1155/S016117120420415X.  Google Scholar

[52]

F. Tchier, Nondeterministic programming theorem,, WSEAS Trans, 5 (2006), 1035.   Google Scholar

[53]

F. Tchier, From Operational to Denotational Demonic Semantics of Nondeterministic While Loops,, 10th WSEAS International Conference on Communications and Computers, (2006).   Google Scholar

[54]

F. Tchier, Demonic fixed points,, Acta Cybernitica Journal, 17 (2006), 533.   Google Scholar

[55]

F. Tchier, Demonic semantics are equal,, in The 2008 International Conference on Foundations of Computer Science (FCS'08), (2008).   Google Scholar

[56]

M. Walicki and S. Medal, Algebraic approches to nondeterminism: An overview,, ACM Computing Surveys, 29 (1997), 30.   Google Scholar

[57]

N. T. E. Ward, A refinement Calculus for Nondeterministic Expressions,, Ph.D thesis, (1994).   Google Scholar

[58]

L. Xu, M. Takeichi and H. Iwasaki, Relational semantics for locally nondeterministic programs,, New Generation Computing, 15 (1997), 339.   Google Scholar

show all references

References:
[1]

C. Aarts, R. Backhouse, P. Hoogendijk, E. Voermans and J. van der Woude, A Relational Theory of Datatypes,, Department of Computing Science, (1992).   Google Scholar

[2]

R. J. R. Back, On the correctness of refinement in program development,, Thesis, (1978).   Google Scholar

[3]

R. J. R. Back, Combining angels, demons and miracles in program specifications,, Theoretical Computer Science, 100 (1992), 365.  doi: 10.1016/0304-3975(92)90309-4.  Google Scholar

[4]

R. J. R. Back, A continuous semantics for unbounded nondeterminism,, Theoretical Computer Science, 23 (1983), 187.  doi: 10.1016/0304-3975(83)90055-5.  Google Scholar

[5]

R. C. Backhouse and H. Doornbos, Mathematical Induction Made Calculational,, Computing Science Note 94/16, (1994).   Google Scholar

[6]

R. C. Backhouse and J. van der Woude, Demonic operators and monotype factors,, Mathematical Structures in Computer Science, 3 (1993), 417.  doi: 10.1017/S096012950000030X.  Google Scholar

[7]

R. Berghammer, Relational Specification of Data Types and Programs, Technical report 9109,, Fakultät für Informatik, (1991).   Google Scholar

[8]

R. Berghammer and G. Schmidt, Relational specifications,, in Algebraic Logic, (1993), 167.   Google Scholar

[9]

R. Berghammer and H. Zierer, Relational algebraic semantics of deterministic and nondeterministic programs,, Theoretical Computer Science, 43 (1986), 123.  doi: 10.1016/0304-3975(86)90172-6.  Google Scholar

[10]

J. Bharat and T. Pallavi, Compositional semantics for diagrams using constrained objects,, in International Conference No 2, (2317), 94.   Google Scholar

[11]

C. Böhm, On a family of Turing machines and the related programming languages,, ICC Bull., 3 (1964), 185.   Google Scholar

[12]

N. Boudriga, F. Elloumi and A. Mili, On the lattice of specifications: Applications to a specification methodology,, Formal Aspects of Computing, 4 (1992), 544.   Google Scholar

[13]

C. Brink, W. Kahl and G. Schmidt, eds., Relational Methods in Computer Science,, Springer, (1997).  doi: 10.1007/978-3-7091-6510-2.  Google Scholar

[14]

L. H. Chin and A. Tarski, Distributive and modular laws in the arithmetic of relation algebras,, University of California Publications, 1 (1951), 341.   Google Scholar

[15]

B. A. Davey and H. A. Priestley, Introduction to Lattices and Order,, Cambridge Mathematical Textbooks, (1990).   Google Scholar

[16]

W. P. De Roever, Recursive Program Schemes: Semantics and Proof Theory,, Math. Centrum Tracts, (1974).   Google Scholar

[17]

J. Desharnais, B. Möller and F. Tchier, Kleene under a modal demonic star,, Journal of Logic and Algebraic Programming, 66 (2006), 127.  doi: 10.1016/j.jlap.2005.04.006.  Google Scholar

[18]

J. Desharnais, B. Möller and F. Tchier, Kleene under a demonic star,, in 8th International Conference on Algebraic Methodology And Software Technology (AMAST 2000), (2000), 355.  doi: 10.1007/3-540-45499-3_26.  Google Scholar

[19]

J. Desharnais, N. Belkhiter, S. B. M. Sghaier, F. Tchier, A. Jaoua, A. Mili and N. Zaguia, Embedding a demonic semilattice in a relation algebra,, Theoretical Computer Science, 149 (1995), 333.  doi: 10.1016/0304-3975(94)00271-J.  Google Scholar

[20]

J. Desharnais, F. Tchier and R. Khédri, Demonic Relational Semantics of Sequential Programs,, Rapport de recherche DIUL-RR-9406, (1994).   Google Scholar

[21]

J. Desharnais, A. Jaoua, F. Mili, N. Boudriga and A. Mili, A Relational division operator: The conjugate kernel,, Theoretical Comput. Sci., 114 (1993), 247.  doi: 10.1016/0304-3975(93)90074-4.  Google Scholar

[22]

J. Desharnais, Abstract Relational Semantics,, Ph D. thesis, (1989).   Google Scholar

[23]

E. W. Dijkstra, A Discipline of Programming,, Prentice-Hall, (1976).   Google Scholar

[24]

H. Doornbos, Reductivity,, Science of Computer Programming, 26 (1996), 217.  doi: 10.1016/0167-6423(95)00027-5.  Google Scholar

[25]

H. Doornbos, A relational model of programs without the restriction to Egli-Milner monotone constructs,, in IFIP Transactions, (1994), 363.   Google Scholar

[26]

H. Doornbos, R. Backhouse and J. van der Woude, A calculational approach to mathematical induction,, Theoretical Computer Science, 179 (1997), 103.  doi: 10.1016/S0304-3975(96)00154-5.  Google Scholar

[27]

R. W. Floyd, Assigning meanings to programs,, Proceedings AMS Symposium in Applied Mathematics, 19 (1967), 19.   Google Scholar

[28]

M. Frappier, A Relational Basis for Program Construction by Parts,, Dept. of Computer Science, (1994).   Google Scholar

[29]

C. Gunter, Semantics of Programming Languages,, MIT Press, (1992).   Google Scholar

[30]

H. Riis Nielson and F. Nielson, Semantics with Applications: An Appetizer, Undergraduate Topics in Computer Science,, Springer-Verlag New York, (2007).   Google Scholar

[31]

C. A. R. Hoare and J. He, The weakest prespecification, Part I,, Fundamenta Informaticae IX, 9 (1986), 51.   Google Scholar

[32]

C. A. R. Hoare and J. He, The weakest prespecification, Part II,, Fundamenta Informaticae IX, 9 (1986), 217.   Google Scholar

[33]

C. A. R. Hoare, et al., Laws of programming,, Communications of the ACM, 30 (1987), 672.  doi: 10.1145/27651.27653.  Google Scholar

[34]

Y. I. Ianov, On the equivalence and transformation of program schemes,, Dokl. Akad. Nauk, 1 (1958), 8.  doi: 10.1145/368924.368930.  Google Scholar

[35]

J. S. Reich and J. L. Jacob, Relational Denotational Semantics of the While Language,, Department of Computer Science, ().   Google Scholar

[36]

R. D. Maddux, Relation-algebraic semantics,, Theoretical Computer Science, 160 (1996), 1.  doi: 10.1016/0304-3975(95)00082-8.  Google Scholar

[37]

A. Mili, A relational approach to the design of deterministic programs,, Acta Informatica, 20 (1983), 315.  doi: 10.1007/BF00264277.  Google Scholar

[38]

A. Mili, J. Desharnais and F. Mili, Relational heuristics for the design of deterministic programs,, Acta Informatica, 24 (1987), 239.  doi: 10.1007/BF00265990.  Google Scholar

[39]

D. L. Parnas, A generalized control structure and its formal definition,, Communications of the ACM, 26 (1983), 572.  doi: 10.1145/358161.358168.  Google Scholar

[40]

J. Riguet, Programmation et théorie des catégories,, in Proc. ICC Symp. Symbolic Languages in Data Processing, (1962), 83.   Google Scholar

[41]

G. Schmidt, Programs as partial graphs I: Flow equivalence and correctness,, Theoretical Computer Science, 15 (1981), 1.  doi: 10.1016/0304-3975(81)90060-8.  Google Scholar

[42]

G. Schmidt and T. Ströhlein, Relations and Graphs,, EATCS Monographs in Computer Science, (1993).  doi: 10.1007/978-3-642-77968-8.  Google Scholar

[43]

E. Sekerinski, A calculus for predicative programming,, in Second International Conf. on the Mathematics of Program Construction, (1992), 302.  doi: 10.1007/3-540-56625-2_20.  Google Scholar

[44]

A. Tarski, A lattice-theoretical fixpoint theorem and its applications,, Pacific Journal of Mathematics, 5 (1955), 285.  doi: 10.2140/pjm.1955.5.285.  Google Scholar

[45]

A. Tarski, On the calculus of relations,, J. Symbolic Logic, 6 (1941), 73.  doi: 10.2307/2268577.  Google Scholar

[46]

F. Tchier and J. Desharnais, A generalisation of a theorem of Mills,, in Proceedings of the Tenth International Symposium on Computer and Information Sciences, (1995), 27.   Google Scholar

[47]

F. Tchier, Sémantiques Relationnelles Démoniaques et Vérification de Boucles Non Déterministes,, Ph. D. thesis, (1996).   Google Scholar

[48]

F. Tchier and J. Desharnais, 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, (1999), 31.  doi: 10.1109/SESD.1999.781109.  Google Scholar

[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).   Google Scholar

[50]

F. Tchier, While loop demonic relational semantics monotype/residual style,, 2003 International Conference on Software Engineering Research and Practice (SERP'03), (2003).   Google Scholar

[51]

F. Tchier, Demonic Semantics: Using monotypes and residuals,, International Journal of Mathematics and Mathematical Sciences, 3 (2004), 135.  doi: 10.1155/S016117120420415X.  Google Scholar

[52]

F. Tchier, Nondeterministic programming theorem,, WSEAS Trans, 5 (2006), 1035.   Google Scholar

[53]

F. Tchier, From Operational to Denotational Demonic Semantics of Nondeterministic While Loops,, 10th WSEAS International Conference on Communications and Computers, (2006).   Google Scholar

[54]

F. Tchier, Demonic fixed points,, Acta Cybernitica Journal, 17 (2006), 533.   Google Scholar

[55]

F. Tchier, Demonic semantics are equal,, in The 2008 International Conference on Foundations of Computer Science (FCS'08), (2008).   Google Scholar

[56]

M. Walicki and S. Medal, Algebraic approches to nondeterminism: An overview,, ACM Computing Surveys, 29 (1997), 30.   Google Scholar

[57]

N. T. E. Ward, A refinement Calculus for Nondeterministic Expressions,, Ph.D thesis, (1994).   Google Scholar

[58]

L. Xu, M. Takeichi and H. Iwasaki, Relational semantics for locally nondeterministic programs,, New Generation Computing, 15 (1997), 339.   Google Scholar

[1]

Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045

[2]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021014

2019 Impact Factor: 1.233

Metrics

  • PDF downloads (44)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]