Comparing free algebras in Topological and Classical Domain Theory

We compare how computational effects are modelled in Classical Domain Theory and Topological Domain Theory. Both of these theories provide powerful toolkits for denotational semantics: Classical Domain Theory having been introduced by Scott, and well established and developed since; Topological Domain Theory being a generalization in which topologies more general than the Scott-topology are admitted. Computational effects can be modelled using free algebra constructions, according to Plotkin and Power, and we show that for a wide range of computational effects, including all the classical powerdomains, this free algebra construction coincides in Classical and Topological Domain Theory, when restricted to countably-based continuous domains.     

Uniform Closures: Order-Theoretically Reconstructing Logic Program Semantics and Abstract Domain Refinements

The notion of uniform closure operator is introduced, and it is shown how this concept surfaces in two different areas of application of abstract interpretation, notably in semantics design for logic programs and in the theory of abstract domain refinements. In logic programming, uniform closures permit generalization, from an order-theoretic perspective, of the standard hierarchy of declarative semantics. In particular, we show how to reconstruct the model-theoretic characterization of the well-known s-semantics using pure order-theoretic concepts only. As far as the systematic refinement operators on abstract domains are concerned, we show that uniform closures capture precisely the property of a refinement of being invertible, namely of admitting a related operator that simplifies as much as possible a given abstract domain of input for that refinement. Exploiting the same argument used to reconstruct the s-semantics of logic programming, we yield a precise relationship between refinements and their inverse operators: we demonstrate that they form an adjunction with respect to a conveniently modified complete order among abstract domains.     

State space analysis of Petri nets with relation-algebraic methods

A large variety of systems can be modelled by Petri nets. Their formal semantics are based on linear algebra which in particular allows the calculation of a Petri net’s state space. Since state space explosion is still a serious problem, efficiently calculating, representing, and analysing the state space is mandatory. We propose a formal semantics of Petri nets based on executable relation-algebraic specifications. Thereupon, we suggest how to calculate the markings reachable from a given one simultaneously. We provide an efficient representation of reachability graphs and show in a correct-by-construction approach how to efficiently analyse their properties. Therewith we cover two aspects: modelling and model checking systems by means of one and the same logic-based approach. On a practical side, we explore the power and limits of relation-algebraic concepts for concurrent system analysis.     

Unique fixed points vs. least fixed points

The aim of this paper is to compare two approaches to the semantics of programming languages: the least fixed point approach, and the unique fixed point approach. Briefly speaking, we investigate here the problem of existence of extensions of algebras with the unique fixed point property to ordered algebras with the least fixed point property, that preserve the fixed point solutions. We prove that such extensions always exist, the construction of a free extension is given. It is also shown that in some cases there is no ‘faithful’ extension, i.e. some elements of a carrier are always collapsed.     

Coalgebraic semantics for timed processes

We give a coalgebraic formulation of timed processes and their operational semantics. We model time by a monoid called a “time domain”, and we model processes by “timed transition systems”, which amount to partial monoid actions of the time domain or, equivalently, coalgebras for an “evolution comonad” generated by the time domain. All our examples of time domains satisfy a partial closure property, yielding a distributive law of a monad for total monoid actions over the evolution comonad, and hence a distributive law of the evolution comonad over a dual comonad for total monoid actions. We show that the induced coalgebras are exactly timed transition systems with delay operators. We then integrate our coalgebraic formulation of time qua timed transition systems into Turi and Plotkin’s formulation of structural operational semantics in terms of distributive laws. We combine timing with action via the more general study of the combination of two arbitrary sorts of behaviour whose operational semantics may interact. We give a modular account of the operational semantics for a combination induced by that of each of its components. Our study necessitates the investigation of products of comonads. In particular, we characterise when a monad lifts to the category of coalgebras for a product comonad, providing constructions with which one can readily calculate.     

Timing and causality in process algebra

 There has been considerable controversy in concurrency theory between the ‘interleaving’ and ‘true concurrency’ schools. The former school advocates associating a transition system with a process which captures concurrent execution via the interleaving of occurrences; the latter adopts more complex semantic structures to avoid reducing concurrency to interleaving. In this paper we show that the two approaches are not irreconcilable. We define a timed process algebra where occurrences are associated with intervals of time, and give it a transition system semantics. This semantics has many of the advantages of the interleaving approach; the algebra admits an expansion theorem, and bisimulation semantics can be used as usual. Our transition systems, however, incorporate timing information, and this enables us to express concurrency: merely adding timing appropriately generalises transition systems to asynchronous transition systems, showing that time gives a link between true concurrency and interleaving. Moreover, we can provide a complete axiomatisation of bisimulation for our algebra; a result that is often problematic in a timed setting. Another advantage of incorporating timing information into the calculus is that it allows a particularly simple definition of action refinement; this we present. The paper concludes with a comparison of the equivalence we present with those in the literature, and an example system specification in our formalism. Received December 20, 1993/February 23, 1995     

Querying Weak Instances Under Extension Chase Semantics: A Complete Solution

The problem of computing windows using relational expressions has been solved only in certain cases in which the chase semantics and the extension chase semantics of the database coincide. However, the general problem of computing windows under either chase semantics or extension chase semantics, but without restrictions, remained an open problem. In this paper we present a complete solution of the general problem, under extension chase semantics. Our solution is complete in the sense that it does not require any assumption on the database scheme or on the database state. It follows that our approach subsumes previous approaches, and we exhibit cases in which our approach correctly computes the windows, while previous approaches fail to do so. Moreover, the efficiency of our approach lies in the fact that it uses only those relation schemes and only those functional dependencies that are necessary in the computation of windows. The main technique employed by our approach is a least fixpoint construction using the notion of cover (a cover being a set of relation schemes satisfying certain properties). The proposed technique can be implemented using relational algebra plus recursion.     

An initial algebra approach to term rewriting systems with variable binders

We present an extension of first-order term rewriting systems. It involves variable binding in the term language. We develop systems called binding term rewriting systems (BTRSs) in a stepwise manner. First we present the term language, then formulate equational logic. Finally, we define rewriting systems. This development is novel because we follow the initial algebra approach in an extended notion of Σ-algebras in various functor categories. These are based on Fiore-Plotkin-Turi’s presheaf semantics of variable binding and Lüth-Ghani’s monadic semantics of term rewriting systems. We characterise the terms, equational logic and rewrite systems for BTRSs as initial algebras in suitable categories. Then, we show an important rewriting property of BTRSs: orthogonal BTRSs are confluent. Moreover, by using the initial algebra semantics, we give a complete characterisation of termination of BTRSs. Finally, we discuss our design choice of BTRSs from a semantic perspective. An erlier version appeared in Proc. Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP2003).     

Linear, Branching Time and Joint Closure Semantics for Temporal Logic

Temporal logic can be used to describe processes: their behaviour ischaracterized by a set of temporal models axiomatized by a temporaltheory. Two types of models are most often used for this purpose: linearand branching time models. In this paper a third approach, based onsocalled joint closure models, is studied using models which incorporateall possible behaviour in one model. Relations between this approach andthe other two are studied. In order to define constructions needed torelate branching time models, appropriate algebraic notions are defined(in a category theoretical manner) and exploited. In particular, thenotion of joint closure is used to construct one model subsuming a setof models. Using this universal algebraic construction we show that aset of linear models can be merged to a unique branching time model.Logical properties of the described algebraic constructions are studied.The proposed approach has been successfully aplied to obtain anappropriate semantics for non-monotonic reasoning processes based ondefault logic. References are discussed that show the details of theseapplications.     

Topological operators: a relaxed query processing approach

Relaxation and approximation techniques have been proposed as approaches for improving the quality of query results, in terms of completeness and accuracy, in environments where the user may not be able to specify the query in a complete and exact way, since data are quite heterogeneous or she may not know all the characteristics of data at hand. This problem, mainly addressed for relational and XML data, is nowadays quite relevant also for geo-spatial data, due to their increasing usage in highly critical decisional processes. Among geo-spatial queries, those based on spatial and more precisely topological relations are currently used in an increasing number of applications. As far as we know, no approach has been proposed so far for relaxing queries based on topological predicates when they return an empty or insufficient answer, in order to improve result quality and user satisfaction. In this paper, we consider this problem and we present a general relaxation strategy for, possibly multi-domain, topological selection and join queries. Two specific semantics are also provided: the first applies the minimum amount of relaxation in order to get an acceptable answer; the second relaxes the given query of a certain fixed amount, depending on the considered topological predicate. Index-based processing algorithms, for efficiently executing relaxed queries based on the proposed semantics, are also presented and a specific topological similarity function, to be used for relaxation purposes, is proposed. Experimental results show that the overhead given by query relaxation is acceptable.     

Formalisations and applications of BPMN

We present two formalisations of the Business Process Modelling Notation (BPMN). In particular, we introduce a semantic model for BPMN in the process algebra CSP; we then study an augmentation of this model in which we introduce relative timing information, allowing one to specify timing constraints on concurrent activities. By exploiting CSP refinement, we are able to show some relationships between the timed and the untimed models. We then describe a novel empirical studies’ model, and the transformation to BPMN, allowing one to apply our formal semantics for analysing different kinds of workflows. To provide a better facility for describing behaviour specification about a BPMN diagram, we also present a pattern-based approach using which a workflow designer could specify properties which could otherwise be difficult to express. Our approach is specifically designed to allow behavioural properties of BPMN diagrams to be mechanically verified via automatic model checking as provided by the FDR tool. We use two examples to illustrate our approach.     

Order and metric in the stream semantics of elemental concurrency

Summary Two denotational semantics for a language with simple concurrency are presented. The language has parallel composition in the form of the shuffle operation, in addition to the usual sequential concepts including full recursion. Two linear time models, both involving sets of finite and infinite streams, are given. The first model is order-theoretic and based on the Smyth order. The second model employs complete metric spaces. Various technical results are obtained relating the order-theoretic and metric notions. The paper culminates in the proof that the two semantics for the language considered coincide. The paper completes previous investigations of the same language, establishing the equivalence of altogether four semantic models for it.     

基于进程代数的构件语义标注技术研究

针对组合构件的语义标注问题,提出基于进程代数的自动标注方法,以减小构件库开发人员手工标注大粒度组合构件语义的工作量。采用本体描述构件的语义,对于不同结构的组合行为,通过进程演算抽取交互行为的执行序列,给出组合构件语义的抽取、合成方法及相应的语义标注算法。将该技术集成到JTangComponent平台上进行实验,结果标明其提高了语义标注的自动化程度,可以为复用构件提供语义保障。     

Topological Perspective on the Hybrid Proof Rules

We consider the non-orthodox proof rules of hybrid logic from the viewpoint of topological semantics. Topological semantics is more general than Kripke semantics. We show that the hybrid proof rule BG is topologically not sound. Indeed, among all topological spaces the BG rule characterizes those that can be represented as a Kripke frame (i.e., the Alexandroff spaces). We also demonstrate that, when the BG rule is dropped and only the Name rule is kept, one can prove a general topological completeness result for hybrid logics axiomatized by pure formulas. Finally, we indicate some limitations of the topological expressive power of pure formulas. All results generalize to neighborhood frames.     

A sound and complete theory of graph transformations for service programming with sessions and pipelines

Graph transformation techniques, the Double-Pushout (DPO) approach in particular, have been successfully applied in the modeling of concurrent systems. In this area, a research thread has addressed the definition of concurrent semantics for process calculi. In this paper, we propose a theory of graph transformations for service programming with sophisticated features such as sessions and pipelines. Through graph representation of CaSPiS, a recently proposed process calculus, we show how graph transformations can cope with advanced features of service-oriented computing, such as several logical notions of scoping together with the interplay between linking and containment. We first exploit a graph algebra and set up a graph model that supports graph transformations in the DPO approach. Then, we show how to represent CaSPiS processes as hierarchical graphs in the graph model and their behaviors as graph transformation rules. Finally, we provide the soundness and completeness results of these rules with respect to the reduction semantics of CaSPiS.     

Towards a theory of mathematical operational semantics

Turi and Plotkin gave a precise mathematical formulation of a notion of structural operational semantics in their paper “Towards a mathematical operational semantics.” Starting from that definition and at the level of generality of that definition, we give a mathematical formulation of some of the basic constructions one makes with structural operational semantics. In particular, given a single-step operational semantics, as is the spirit of their work, one composes transitions and considers streams of transitions in order to study the dynamics induced by the operational semantics. In all their leading examples, it is obvious that one can do that and it is obvious how to do it. But if their definition is to be taken seriously, one needs to be able to make such constructions at the level of generality of their definition rather than case-by-case. So this paper does so for several of the basic constructions associated with structural operational semantics, in particular those required in order to speak of a stream of transitions and hence of dynamics.     

Toward a computational interpretation of situation semantics1

Situation semantics proposes novel and attractive treatments for several problem areas of natural language semantics, such as efficiency (context sensitivity) and prepositional attitude reports. Its focus on the information carried by utterances makes the approach very promising for accounting for pragmatic phenomena. However, situation semantics seems to oppose several basic assumptions underlying current approaches to natural language processing and the design of intelligent systems in general. It claims that efficiency undermines the standard notions of logical form, entailment, and proof theory, and objects to the view that mental processes necessarily involve internal representations. The paper attempts to clarify these issues and discusses the impact of situation semantics’ criticisms for natural language processing, knowledge representation, and reasoning. I claim that the representational approach is the only currently practical one for the design of large intelligent systems, but argue that the representations used should be efficient in order to account for the system's embedding in its environment. The paper concludes by stating some constraints that a computational interpretation of situation semantics should obey and discussing remaining problems.     

Explication and semantic querying of enterprise information systems

Many researches show that the ability of independent, heterogeneous enterprises’ information systems to interoperate is related to the challenges of making their semantics explicit and formal, so that the messages are not merely exchanged, but interpreted, without ambiguity. In this paper, we present an approach to overcome those challenges by developing a method for explication of the systems’ implicit semantics. We define and implement the method for the generation of local ontologies, based on the databases of their systems. In addition, we describe an associated method for the translation between semantic and SQL queries, a process in which implicit semantics of the EIS’s databases and explicit semantics of the local ontologies become interrelated. Both methods are demonstrated in the case of creating the local ontology and the semantic querying of OpenERP Enterprise Resource Planning system, for the benefit of the collaborative supply chain planning.     

Topological spatial relations for active visual search

If robots are to assume their long anticipated place by humanity’s side and be of help to us in our partially structured environments, we believe that adopting human-like cognitive patterns will be valuable. Such environments are the products of human preferences, activity and thought; they are imbued with semantic meaning. In this paper we investigate qualitative spatial relations with the aim of both perceiving those semantics, and of using semantics to perceive. More specifically, in this paper we introduce general perceptual measures for two common topological spatial relations, “on” and “in”, that allow a robot to evaluate object configurations, possible or actual, in terms of those relations. We also show how these spatial relations can be used as a way of guiding visual object search. We do this by providing a principled approach for indirect search in which the robot can make use of known or assumed spatial relations between objects, significantly increasing the efficiency of search by first looking for an intermediate object that is easier to find. We explain our design, implementation and experimental setup and provide extensive experimental results to back up our thesis.     

Process algebra with action dependencies

In this paper, we present a process algebra with a minimal form of semantics for actions given by dependencies. Action dependencies are interpreted in the Mazurkiewicz sense: independent actions should be able to commute, or (from a different perspective) should be unordered, whereas dependent actions are always ordered. In this approach, the process algebra operators are used to describe the conceptual behavioural structure of the system, and the action dependencies determine the minimal necessary orderings and thereby the additionally possible parallelism within this structure. In previous work on the semantics of specifications using Mazurkiewicz dependencies, the main interest has been on linear time. We present in this paper a branching time semantics, both operationally and denotationally. For this purpose, we introduce a process algebra that incorporates, besides some standard operators, also an operator for action refinement. For interpreting the operators in the presence of action dependencies, a new concept of partial termination has to be developed. We show consistency of the operational and denotational semantics; furthermore, we give a axiomatisation of bisimilarity, which is complete for finite terms. Some small examples demonstrate the flexibility of this process algebra in the design of distributed reactive systems. Received: 19 November 1998 / 18 July 2001