Paper Info
Title
Demonic semantics: using monotypes and residuals
Abstract
is given by these operators will go wrong; it is the demonic semantics. This type of seman- tics is known at least since Dijkstra's introduction of the language of guarded commands. Recently, there has been a growing interest in demonic relational semantics of sequential programs. Usually, a construct is given an ad hoc semantic definition based on an intuitive understanding of its behavior. In this note, we show how the notion of relational flow dia- gram (essentially a matrix whose entries are relations on the set of states of the program), introduced by Schmidt, can be used to give a single demonic definition for a wide range of programming constructs. This research had originally been carried out by J. Desharnais and F. Tchier (1996) in the same framework of the binary homogeneous relations. We show that all the results can be generalized by using the monotypes and the residuals introduced by Desharnais et al. (2000). 2000 Mathematics Subject Classification: 18C10, 18C50, 68Q55, 68Q65, 03B70, 06B35. 1. Introduction. The approaches to semantics are categorized as operational, ax- iomatic, or denotational. We will be concerned with the operational and the denota- tional semantics of nondeterministic programs. The operational semantics is described by the relation between the initial and final states. In our case, we consider the worst execution of the program; that is, we suppose that the program behaves as badly as possible according to the demonic relational semantics . Usually this last one is given an ad hoc semantics definition based on an intuitive understanding of the behavior of the program. Denotational semantics has been introduced by Scott and Strachey. To give the denotational semantics, we associate to a program a mathematical object. In our case, this object is a flow diagram which is a graph whose arrows are weighted by the different steps of the program. The operations are "the demonic choice" and "de- monic composition." In this note, we show how the notion of the flow diagram can be exploited to give single demonic operational semantics (with only demonic operators) for a wide range of programming constructs.
Year
DOI
Venue
2004
10.1155/S016117120420415X
Int. J. Math. Mathematical Sciences
Field
DocType
Volume
Topology,Algebra,Kripke semantics,Matrix (mathematics),Homogeneous,Theoretical computer science,Operator (computer programming),Mathematics,Semantics,Dijkstra's algorithm,Data flow diagram,Binary number
Journal
2004
Issue
Citations 
PageRank 
3
0
0.34
References 
Authors
14
1
Name
Order
Citations
PageRank
Fairouz Tchier1588.95