Refinement algebra with dual operator

Algebras of imperative programming languages have been successful in reasoning about programs. In general an algebra of programs is an algebraic structure with programs as elements and with program compositions (sequential composition, choice, skip) as algebra operations. Various versions of these algebras were introduced to model partial correctness, total correctness, refinement, demonic choice, and other aspects. We introduce here an algebra which can be used to model total correctness, refinement, demonic and angelic choice. The basic model of our algebra are monotonic Boolean transformers (monotonic functions from a Boolean algebra to itself).     

Algebras of modal operators and partial correctness

Modal Kleene algebras are Kleene algebras enriched by forward and backward box and diamond operators. We formalise the symmetries of these operators as Galois connections, complementarities and dualities. We study their properties in the associated operator algebras and show that the axioms of relation algebra are theorems at the operator level. Modal Kleene algebras provide a unifying semantics for various program calculi and enhance efficient cross-theory reasoning in this class, often in a very concise pointfree style. This claim is supported by novel algebraic soundness and completeness proofs for Hoare logic and by connecting this formalism with an algebraic decision procedure.     

Refinement algebra for probabilistic programs

We identify a refinement algebra for reasoning about probabilistic program transformations in a total-correctness setting. The algebra is equipped with operators that determine whether a program is enabled or terminates respectively. As well as developing the basic theory of the algebra we demonstrate how it may be used to explain key differences and similarities between standard (i.e. non-probabilistic) and probabilistic programs and verify important transformation theorems for probabilistic action systems.     

Dynamic effect algebras and their representations

For lattice effect algebras, the so-called tense operators were already introduced by Chajda and Kola?ík. Tense operators express the quantifiers “it is always going to be the case that” and “it has always been the case that” and hence enable us to express the dimension of time in the logic of quantum mechanics. We present an axiomatization of these tense operators and prove that in every effect algebra can be introduced tense operators which, for non-complete lattice effect algebras, can be only partial mappings. An effect algebra equipped with tense operators reflects changes of quantum events from past to future. A crucial problem concerning tense operators is their representation. Having an effect algebra with tense operators, we can ask if there exists a frame such that each of these operators can be obtained by our construction. We solve this problem for (strict) dynamic effect algebras having a full set of homorphisms into a complete lattice effect algebra.     

Synchronous Kleene algebra

The work presented here investigates the combination of Kleene algebra with the synchrony model of concurrency from Milner’s SCCS calculus. The resulting algebraic structure is called synchronous Kleene algebra. Models are given in terms of sets of synchronous strings and finite automata accepting synchronous strings. The extension of synchronous Kleene algebra with Boolean tests is presented together with models on sets of guarded synchronous strings and the associated automata on guarded synchronous strings. Completeness w.r.t. the standard interpretations is given for each of the two new formalisms. Decidability follows from completeness. Kleene algebra with synchrony should be included in the class of true concurrency models. In this direction, a comparison with Mazurkiewicz traces is made which yields their incomparability with synchronous Kleene algebras (one cannot simulate the other). On the other hand, we isolate a class of pomsets which captures exactly synchronous Kleene algebras. We present an application to Hoare-like reasoning about parallel programs in the style of synchrony.     

Region–based theory of discrete spaces: A proximity approach

We introduce Boolean proximity algebras as a generalization of Efremovič proximities which are suitable in reasoning about discrete regions. Following Stone’s representation theorem for Boolean algebras, it is shown that each such algebra is isomorphic to a substructure of a complete and atomic Boolean proximity algebra. Co-operation was supported by EC COST Action 274 “Theory and Applications of Relational Structures as Knowledge Instruments” (TARSKI), , and NATO Collaborative Linkage Grant PST.CLG 977641.     

粗代数研究

在粗糙集的代数方法研究中,一个重要的方面是从粗糙集的偶序对((下近似集,上近似集()表示入手,通过定义偶序对的基本运算,从而构造出相应粗代数,并寻找能够抽象刻画偶序对性质的一般代数结构.其中最有影响的粗代数分别是粗双Stone代数、粗Nelson代数和近似空间代数,它们对应的一般代数结构分别是正则双Stone代数、半简单Nelson代数和预粗代数.通过建立这些粗代数中算子之间的联系,证明了:(a) 近似空间代数可转化为半简单Nelson代数和正则双Stone代数;(b) 粗Nelson代数可转化为预粗代数和正则双Stone代数;(c) 粗双Stone代数可化为预粗代数和半简单Nelson代数,从而将3个不同角度的研究统一了起来.     

Solving and factoring boundary problems for linear ordinary differential equations in differential algebras

We present a new approach for expressing and solving boundary problems for linear ordinary differential equations in the language of differential algebras. Starting from an algebra with a derivation and integration operator, we construct an algebra of linear integro-differential operators that is expressive enough for specifying regular boundary problems with arbitrary Stieltjes boundary conditions as well as their solution operators.     

A Process Calculus with Finitary Comprehended Terms

We introduce the notion of an ACP process algebra and the notion of a meadow enriched ACP process algebra. The former notion originates from the models of the axiom system ACP. The latter notion is a simple generalization of the former notion to processes in which data are involved, the mathematical structure of data being a meadow. Moreover, for all associative operators from the signature of meadow enriched ACP process algebras that are not of an auxiliary nature, we introduce variable-binding operators as generalizations. These variable-binding operators, which give rise to comprehended terms, have the property that they can always be eliminated. Thus, we obtain a process calculus whose terms can be interpreted in all meadow enriched ACP process algebras. Use of the variable-binding operators can have a major impact on the size of terms.     

Very true operators in effect algebras

We introduce the concept of very true operator on an effect algebra. Although an effect algebra is only partial, we define it in the way which is in accordance with traditional definitions in residuated lattices or basic algebras. This is possible if we require monotonicity as an additional condition. We prove that very true operators on effect algebras can be characterized by means of certain subsets which are conditionally complete.     

Point algebras for temporal reasoning: Algorithms and complexity

We investigate the computational complexity of temporal reasoning in different time models such as totally-ordered, partially-ordered and branching time. Our main result concerns the satisfiability problem for point algebras and point algebras extended with disjunctions—for these problems, we identify all tractable subclasses. We also provide a number of additional results; for instance, we present a new time model suitable for reasoning about systems with a bounded number of unsynchronized clocks, we investigate connections with spatial reasoning and we present improved algorithms for deciding satisfiability of the tractable point algebras.     

Multiple-Agent Perspectives in Reasoning About Situations for Context-Aware Pervasive Computing Systems

In open heterogeneous context-aware pervasive computing systems, suitable context models and reasoning approaches are necessary to enable collaboration and distributed reasoning among agents. This paper proposes, develops, and demonstrates the following: 1) a novel context model and reasoning approach developed with concepts from the state-space model, which describes context and situations as geometrical structures in a multidimensional space; and 2) a context algebra based on the model, which enables distributed reasoning by merging and partitioning context models that represent different perspectives of computing entities over the object of reasoning. We show how merging and reconciling different points of view over context enhances the outcomes of reasoning about the context. We develop and evaluate our proposed algebraic operators and reasoning approaches with cases using real sensors and with simulations. We embed agents and mobile agents with these modeling and reasoning capabilities, thus facilitating context-aware and adaptive mobile agents operating in open pervasive environments.     

A sketch of a dynamic epistemic semiring

This paper proposes a semiring formulation for reasoning about an agent’s changing beliefs: a dynamic epistemic semiring (DES). A DES is a modal semiring extended with epistemic-action operators. The paper concentrates on the revision operator by proposing an axiomatisation, developing a basic calculus and deriving the classical AGM revision axioms in the algebra. Iterated action is also considered.     

A Comparison of Inferences about Containers and Surfaces in Small-Scale and Large-Scale Spaces

Inference mechanisms about spatial relations constitute an important aspect of spatial reasoning as they allow users to derive unknown spatial information from a set of known spatial relations. When formalized in the form of algebras, spatial-relation inferences represent a mathematically sound definition of the behavior of spatial relations, which can be used to specify constraints in spatial query languages. Current spatial query languages utilize spatial concepts that are derived primarily from geometric principles, which do not necessarily match with the concepts people use when they reason and communicate about spatial relations. This paper presents an alternative approach to spatial reasoning by starting with a small set of spatial operators that are derived from concepts closely related to human cognition. This cognitive foundation comes from the behavior of image schemata, which are cognitive structures for organizing people's experiences and comprehension. From the operations and spatial relations of a small-scale space, a container–surface algebra is defined with nine basic spatial operators—inside, outside, on, off, their respective converse relations—contains, excludes, supports, separated_from, and the identity relation equal. The container–surface algebra was applied to spaces with objects of different sizes and its inferences were assessed through human-subject experiments. Discrepancies between the container–surface algebra and the human-subject testing appear for combinations of spatial relations that result in more than one possible inference depending on the relative size of objects. For configurations with small- and large-scale objects larger discrepancies were found because people use relations such as part of and at in lieu of in. Basic concepts such as containers and surfaces seem to be a promising approach to define and derive inferences among spatial relations that are close to human reasoning.     

Theorems on the structure of finite dimensional estimation algebras

In this paper we proved several theorems concerning the structure of finite dimensional estimation algebras. In particular, under proper technical assumptions, we proved the following: (1) The observation of a filtering system must be linear if the estimation algebra is finite dimensional. (2) All elements of a finite dimensional estimation algebra belong to a special class of polynomial differential operators. (3) All finite dimensional estimation algebras are solvable.     

On the complemented disk algebra

The importance of relational methods in temporal and spatial reasoning has been widely recognised in the last two decades. A quite large part of contemporary spatial reasoning is concerned with the research of relation algebras generated by the “part of” and “connection” relations in various domains. This paper is devoted to the study of one particular relation algebra appeared in the literature, viz. the complemented disk algebra. This algebra was first described by Düntsch [I. Düntsch, A tutorial on relation algebras and their application in spatial reasoning, Given at COSIT, August 1999, Available from: <http://www.cosc.brocku.ca/~duentsch/papers/relspat.html>] and then, Li et al. [Y. Li, S. Li, M. Ying, Relational reasoning in the Region Connection Calculus, Preprint, 2003, Available from: http://arxiv.org/abs/cs/0505041] showed that closed disks and their complements provides a representation. This set of regions is rather restrictive and, thus, of limited practical values. This paper will provide a general method for generating representations of this algebra in the framework of Region Connection Calculus. In particular, connected regions bounded by Jordan curves and their complements is also such a representation.     

补偿通信顺序进程的扩展及失败发散语义

补偿通信顺序进程(cCSP)是通信顺序进程用于长事务建模的扩展,可用来描述服务计算中的编制程序,比如WS-BPEL程序。目前,cCSP只有操作语义和基于迹的指称语义,对死锁和发散行为的推理支持不够。本文扩展了cCSP,引入新的组合操作子,给出扩展cCSP的失败发散语义;并根据该语义,给出新引入组合操作子的重要代数规则,用于语义的理解和佐证。最后,给出一个案例描述用于展示扩展cCSP。     

Granularity in Relational Formalisms—With Application to Time and Space Representation

Temporal and spatial phenomena can be seen at a more or less precise granularity, depending on the kind of perceivable details. As a consequence, the relationship between two objects may differ depending on the granularity considered. When merging representations of different granularity, this may raise problems. This paper presents general rules of granularity conversion in relation algebras. Granularity is considered independently of the specific relation algebra, by investigating operators for converting a representation from one granularity to another and presenting six constraints that they must satisfy. The constraints are shown to be independent and consistent and general results about the existence of such operators are provided. The constraints are used to generate the unique pairs of operators for converting qualitative temporal relationships (upward and downward) from one granularity to another. Then two fundamental constructors (product and weakening) are presented: they permit the generation of new qualitative systems (e.g. space algebra) from existing ones. They are shown to preserve most of the properties of granularity conversion operators.     

A syntactic theory of sequential control

Sequential control operators like J and call/cc are often found in implementations of the λ-calculus as a programming language. Their semantics is always defined by the evaluation function of an abstract machine. We show that, given such a machine semantics, one can derive an algebraic extension of the λ_υ-calculus. The extended calculus satisfies the diamond property and contains a Church-Rosser subcalculus. This underscores that the interpretation of control operators is to a certain degree independent of a specific evaluation strategy. We also prove a standardization theorem and use it to investigate the correspondence between the machine and the calculus. Together, the calculus and the rewriting machine form a syntactic theory of control, which provides a natural basis for reasoning about programs with nonfunctional control operators.