A denotational semantics for Handel-C

We present a denotational semantics for a fully functional subset of the Handel-C hardware compilation language (Celoxica Ltd., Handel-C Language Reference Manual, v3.0, 2002, ), based on the concept of typed assertion traces. We motivate the choice of semantic domains by illustrating the complexities of the behaviour of the language, paying particular attention to the prialt (priority-alternation) construct of Handel-C. We then define the typed assertion traces over an abstract notion of actions, and demonstrate key properties of the key semantic operations on these. The denotational semantics is then given using traces with actions instantiated as state-transformers.     

A UTP semantics for Circus

Circus specifications define both data and behavioural aspects of systems using a combination of Z and CSP constructs. Previously, a denotational semantics has been given to Circus; however, a shallow embedding of Circus in Z, in which the mapping from Circus constructs to their semantic representation as a Z specification, with yet another language being used as a meta-language, was not useful for proving properties like the refinement laws that justify the distinguishing development technique associated with Circus. This work presents a final reference for the Circus denotational semantics based on Hoare and He’s Unifying Theories of Programming (UTP); as such, it allows the proof of meta-theorems about Circus including the refinement laws in which we are interested. Its correspondence with the CSP semantics is illustrated with some examples. We also discuss the library of lemmas and theorems used in the proofs of the refinement laws. Finally, we give an account of the mechanisation of the Circus semantics and of the mechanical proofs of the refinement laws.     

A semantics for Fuzzy Logic

 We present a semantics for certain Fuzzy Logics of vagueness by identifying the fuzzy truth value an agent gives to a proposition with the number of independent arguments that the agent can muster in favour of that proposition. Received: 25 February 1997 / Accepted: 12 March 1997     

A set-theoretic semantics for Clear

Summary A semantics for the Clear specification language is given. The language of set theory is employed to present constructions corresponding to Clear's specification-combining operations, which are then used as the basis for a denotational semantics. This is in contrast to Burstall and Goguen's 1980 semantics which described the meanings of these operations more abstractly via concepts from category theory.     

A multi-tier semantics for Hop

Hop is a multi-tier programming language where the behavior of interacting servers and clients are expressed by a single program. Hop adheres to the standard web programming style where servers elaborate HTML pages containing JavaScript code. This JavaScript code responds locally to user’s interactions but also (following the so-called Ajax style) requests services from remote servers. These services bring back new HTML fragments containing additional JavaScript code replacing or modifying the state of the client. This paper presents a continuation-based denotational semantics for a sequential subset of Hop. Though restricted to a single server and a single client, this semantics takes into account the key feature of Hop namely that the server elaborates client code to be run in the client’s browser. This new client-code dynamically requests services from the server which, again, elaborate new client code to be run in the client’s browser. This semantics details the programming model advocated by Hop and provides a sound basis for future studies such as security of web applications and web continuations.     

The perceived urgency of speech warnings: semantics versus acoustics

The relationship between the semantics of words and the acoustics of the way they are spoken is explored. Actors spoke warning signal words in an urgent, nonurgent and monotone style, and participants rated the urgency of the words. Results showed effects for signal word and style of presentation. Acoustic analysis showed that the urgent words were spoken at higher frequency with a broader pitch range and were louder than the nonurgent or monotone words. These acoustic differences were used to synthesize artificial versions of signal words in urgent and nonurgent formats. The urgent words were rated as more urgent than the nonurgent words, a finding attributable to their differing acoustics. Within each speaking style the words were acoustically the same, yet effects for signal word were found, suggesting that semantics is also important in urgency perception. This research has implications for the design and implementation of speech warning systems, particularly those in which urgency mapping is required.     

A Fixpoint Semantics for Stratified Databases

Przmusinski extended the notion of stratified logic programs,developed by Apt,Blair and Walker,and by van Gelder,to stratified databases that allow both negative premises and disjunctive consequents.However,he did not provide a fixpoint theory for such class of databases.On the other hand,although a fixpoint semantics has been developed by Minker and Rajasekar for non-Horn logic programs,it is tantamount to traditional minimal model semantics which is not sufficient to capture the intended meaning of negation in the premises of clauses in stratified databases.In this paper,a fixpoint approach to stratified databases is developed,which corresponds with the perfect model semantics.Moreover,algorithms are proposed for computing the set of perfect models of a stratified database.     

A structured operational semantics for UML-statecharts

The Unified Modeling Language (UML) has gained wide acceptance in very short time because of its variety of well-known and intuitive graphical notations. However, this comes at the price of an unprecise and incomplete semantics definition. This insufficiency concerns single UML diagram notations on their own as well as their integration. In this paper, we focus on the notation of UML-statecharts. Starting with a precise textual syntax definition, we develop a precise structured operational semantics (SOS) for UML-statecharts. Besides the support of interlevel transitions and in contrast to related work, our semantics definition supports characteristic UML-statechart features like the history mechanism as well as entry and exit actions. Initial submission: 19 February 2002 / Revised submission: 28 October 2002 Published online: 2 December 2002     

A semantics for web services authentication

We consider the problem of specifying and verifying cryptographic security protocols for XML web services. The security specification WS-Security describes a range of XML security elements, such as username tokens, public-key certificates, and digital signatures, amounting to a flexible vocabulary for expressing protocols. To describe the syntax of these elements, we extend the usual XML data model with symbolic representations of cryptographic values. We use predicates on this data model to describe the semantics of security elements and of sample protocols distributed with the Microsoft WSE implementation of WS-Security. By embedding our data model within Abadi and Fournet's applied pi calculus, we formulate and prove security properties with respect to the standard Dolev–Yao threat model. Moreover, we informally discuss issues not addressed by the formal model. To the best of our knowledge, this is the first approach to the specification and verification of security protocols based on a faithful account of the XML wire format.     

A continuous semantics for unbounded nondeterminism

Nondeterminism is introduced into an ordinary iterative programming language by treating procedure calls as nondeterministic assignment statements. The effect of such assignment statements is assumed to be determined solely by the entry-exit specifications of the corresponding procedures. The nondeterminism which this approach yields is not necessarily bounded. The paper discusses the problem of defining a denotational semantic for programming languages with this kind of, possibly unbounded, nondeterminism. As an additional constraint, the semantics is required to be continuous, in the sense that the underlying semantic algebra is continuous. It is shown how such a continuous semantics for unbounded nondeterminism can be derived from a simple operational semantics based on program execution trees.     

A differential semantics for jointree algorithms

A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi-linear functions. According to this approach, belief network inference reduces to a simple process of evaluating and differentiating multi-linear functions. We show here that mainstream inference algorithms based on jointrees are a special case of the approach based on multi-linear functions, in a very precise sense. We use this result to prove new properties of jointree algorithms. We also discuss some practical and theoretical implications of this new finding.     

A procedural semantics for stratified database updates

This paper investigates efficient evaluation of database updates and presents a procedural semantics for stratified update programs that extend stratified logic programs with bulk updates and hypothetical reasoning. Bulk rules with universal quantification in the body allow an arbitrary update to be applied simultaneously for every answer of an arbitrary query. Hypothetical reasoning is supported by testing the success or failure of an update. The procedural semantics offers efficient goal-oriented tabled evaluation of database updates. It guarantees termination for function-free stratified update programs and avoids repeated computation of identical subgoals. This revised version was published online in June 2006 with corrections to the Cover Date.     

A weakest precondition semantics for communicating processes

A weakest precondition semantics for communicating processes is presented, based on a centralized, one-level approach. Semantic equations are given for the CSP constructs and their continuity is proved. The equivalence of two weakest precondition definitions, one with certain order preferences, and another one, preference-free, is shown. The representation of various operational concepts, including delay, is discussed. Several examples of applying the rules are given.     

A possible world semantics for disjunctive databases

The fundamental problem that arises when a ground atom in a disjunctive database is assumed false is discussed. There are basically two different approaches for inferring negative information for disjunctive databases: J. Minker's (1982) generalized closed world assumption (GCWA) and K.A. Ross and R.W. Topor's (1988) disjunctive database rule (DDR). It is argued that neither approach is satisfactory. A database semantics called PWS is proposed. It is shown that for propositional databases with no negative clauses, the problem of determining if a negative ground literal is inferred under the GCWA is co-NP-hard, while the same problem can be solved efficiently under the DDR and PWS. However, in the general case, the problem becomes co-NP-complete for the DDR and PWS. Relationships among GCWA, DDR, and PWS are highlighted. In general, disjunctive clauses are interpreted inclusively under the DDR and unpredictably under the GCWA     

A Formal Semantics for DAI Language NUML

Traditional AI systems are brittle in the sense that they fail miserably when presented with problems even sliphtly outside of their limited range of expertise.A powerful,extensible strategy of Distributed Artificial Intelligence (DAI) for overcoming such bounds is to put the system in a society of systems.So the ability to coordinate group activities of individuals and to communicate between each other is necessary for a language describing DAI systems.Agent-oriented language NUML is such a language.It is a specific kind of object-oriented language.To give formal semantics to NUML,there is the problem to formalise object-oriented programming paradigm which is still open.The theory of higher-order π-calculus is a concurrent computation model with sufficient capability,which provides us a mathematical tool to do the formalization.This paper tries to use higher-order π-calculus to formalise NUML.