On stratified disjunctive programs

We address the problem of a consistent fixpoint semantics for general disjunctive programs restricted to stratifiable programs which do not recurse through negative literals. We apply the nonmonotonic fixpoint theory developed by Apt, Blair and Walker to a closure operatorT ^c and develop a fixpoint semantics for stratified disjunctive programs. We also provide an iterative definition for negation, called the Generalized Closed World Assumption for Stratified programs (GCWAS), and show that our semantics captures this definition. We develop a model-theoretic semantics for stratified disjunctive programs and show that the least state characterized by the fixpoint semantics corresponds to a stable-state defined in a manner similar to the stable-models of Gelfond and Lifschitz. We also discuss a weaker stratification semantics for general disjunctive programs based on the Weak Generalized Closed World Assumption.     

Backtracking in recursive computations

Summary A mathematical (denotational) semantics is constructed for a formalism of recursive equations with the Alternative operator. This formalism enables the combination of recursion and backtracking. The semantics is defined by applying fixpoint theory to set valued functions. We introduce the notion of strategy to produce subsets of the result. Two implementations are suggested using an auxiliary stack, that trade off recomputation time with space in the auxiliary stack. The concept of a sub-fixpoint is introduced, and the implementations are shown to be incomplete even w.r.t. sub-fixpoint values. One special strategy, the leftmost strategy, which stems from problems such as pattern matching or parsing, is discussed.     

Lattice-theoretical fixpoint theorems in morphological image filtering

In mathematical morphology, Matheron has described the complete lattice structure of several classes of increasing (isotone) operators, such as filters. These results can be interpreted in terms of fixpoints of certain types of transformations of the lattice of increasing operators. Moreover, Heijmans and Serra have given conditions for the construction of such operators by convergence of an iteration of increasing operators. We recall some known lattice-theoretical fixpoint ideas originating from Tarski's 1955 paper. A slight elaboration on the underlying methodology leads to the aforementioned results and some others as a consequence of the general theory.     

RKB／PL：C＋＋的持久性扩充

需求工程知识库／ＰＬ——ＲＫＢ／ＰＬ（ｒｅｑｕｉｒｅｍｅｎｔ—ｅｎｇｉｎｅｅｒｉｎｇｋｎｏｗｌｅｄｇｅｂａｓｅ／ＰＬ）是保持Ｃ＋＋原有风格对Ｃ＋＋进行的持久性扩充．为支持对象的持久性,ＲＫＢ／ＰＬ在Ｃ＋＋对象类的基础上扩充了以约束声明加强对象状态的用户监控;引入簇来表达对象类的集合含义;引入集合、簇、簇闭包的遍历机制来支持对象查询．为支持这些语言机制,ＲＫＢ／ＰＬ具有一个由一组ｂｕｉｌｄ—ｉｎ对象类层次、类型信息库及接口函数、系统状态表以及系统服务函数等构成的运行时系统．本文讨论了ＲＫＢ／ＰＬ中这些机制的表示、相应的运行时系统的组成以及它们的主要实现技术．ＲＫＢ／ＰＬ已成功地用于实现“软件需求获取助手ＦＲＡ”系统的需求工程知识库子系统．     

Semantic Forcing in Disjunctive Logic Programs

We propose a semantics for disjunctive logic programs, based on the single notion of forcing. We show that the semantics properly extends, in a natural way, previous approaches. A fixpoint characterization is also provided. We also take a closer look at the relationship between disjunctive logic programs and disjunctive-free logic programs. We present certain criteria under which a disjunctive program is semantically equivalent with its disjunctive-free (shifted) version.     

Linear Embedding for a Quantitative Comparison of Language Expressiveness

We introduce the notion of linear embedding which refines Shapiro's notion of embedding by recasting it in a linear-space based semantics setting. We use this notion to compare the expressiveness of a class of languages that employ asynchronous communication primitives á la Linda. The adoption of a linear semantics in which the observables of a language are linear operators (matrices) representing the programs transition graphs allows us to give quantitative estimates of the different expressive power of languages, thus improving previous results in the field.     

Design and specification of iterators using the swapping paradigm

How should iterators be abstracted and encapsulated in modern imperative languages? We consider the combined impact of several factors on this question: the need for a common interface model for user defined iterator abstractions, the importance of formal methods in specifying such a model, and problems involved in modular correctness proofs of iterator implementations and clients. A series of iterator designs illustrates the advantages of the swapping paradigm over the traditional copying paradigm. Specifically, swapping based designs admit more efficient implementations while offering relatively straightforward formal specifications and the potential for modular reasoning about program behavior. The final proposed design schema is a common interface model for an iterator for any generic collection     

Recursion from iteration

In a simply-typed, call-by-value (CBV) language with first-class continuations, the usual CBV fixpoint operator can be defined in terms of a simple, infinitely-looping iteration primitive. We first consider a natural but flawed definition, based on exceptions and “iterative deepening” of finite unfoldings, and point out some of its shortcomings. Then we present the proper construction using full first-class continuations, with both an informal derivation and a proof that the behavior of the defined operator faithfully mimics a “built-in” recursion primitive. In fact, given an additional uniformity assumption, the construction is a two-sided inverse of the usual definition of iteration from recursion. Continuing, we show that the CBV looping primitive is in fact the direct-style equivalent of a continuation-passing-style fixpoint, and that this correspondence extends all the way to traditional definitions of these operators in terms of reflexive types.     

Specification of iterators

Iterators are defined, and previously published methods for defining their meanings are outlined. It is shown how to use trace specifications to define a common form of iterator module (Alphard-style iterators). A form of specification for an iterator is shown which can capture the key differences between a set and a sequence at a few particular places in the specification. The trace specification of a sequence iterator is compared to an algebraic specification. It is concluded that the algebraic specification is possible but somewhat clumsier. Traces are used to give partial specifications of iterator construct that make sequences of calls on procedural parameters     

A methodology for designing proof rules for fair parallel programs

We propose a methodology for designing sound and complete proof systems for proving progress properties of parallel programs under various fairness assumptions. Our methodology begins with a branching time temporal logic formula (CTL^*) formula that expresses progress under a fairness assumption. The next step obtains an equivalent fixpoint characterization of this CTL^* formula in the-calculus. The final step uses the fixpoint characterizations to extract proof systems for proving progress under the fairness constraint. The methodology guarantees that the proof rules so obtained are sound and relatively complete in the sense of Cook.     

A logic for the specification and proof of regular controllable processes of CCS

Summary This work has been motivated by the following general problem: find logics for the specification and proof of programs, described by terms of some algebra with given congruence relation. This relation is supposed to define a satisfactory concept for the behavioural comparison of programs. We require these logics to be adequate with respect to the term language, in the sense that two programs, behaviourally equivalent satisfy the same formulas and conversely. The term language considered is the subset of controllable, regular terms of CCS, on a vocabulary of actions A, with observational congruence. A term is said to be controllable if it is congruent to some term without occurrence of . We obtain an adequate logic whose language of formulas is obtained from constants true, false and ¦Nil¦ by using operators , , fixpoint operators, + and a for aA; the latter can be considered as extensions of the operators + and a for aA of CCS. As a result, controllable CCS terms can be considered as formulas of this logic and the problem of program verification is reduced to the proof of the validity of a formula.     

Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation

Disjunctive logic programs have become a powerful tool in knowledge representation and commonsense reasoning. This paper focuses on stable model semantics, currently the most widely acknowledged semantics for disjunctive logic programs. After presenting a new notion of unfounded sets for disjunctive logic programs, we provide two declarative characterizations of stable models in terms of unfounded sets. One shows that the set of stable models coincides with the family of unfounded-free models (i.e., a model is stable iff it contains no unfounded atoms). The other proves that stable models can be defined equivalently by a property of their false literals, as a model is stable iff the set of its false literals coincides with its greatest unfounded set. We then generalize the well-founded operator to disjunctive logic programs, give a fixpoint semantics for disjunctive stable models and present an algorithm for computing the stable models of function-free programs. The algorithm's soundness and completeness are proved and some complexity issues are discussed.     

Fixing Zeno gaps

In computer science, fixpoints play a crucial role. Most often least and greatest fixpoints are sufficient. However, there are situations where other ones are needed. In this paper, we study, on an algebraic base, a special fixpoint of the function f(x)=a⋅x that describes infinite iteration of an element a. We show that the greatest fixpoint is too imprecise. Special problems arise if the iterated element contains the possibility of stepping on the spot (e.g. skip in a programming language) or if it allows Zeno behaviour. We present a construction for a fixpoint that captures these phenomena in a precise way. The theory is presented and motivated using an example from hybrid system analysis.     

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.     

Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

The nested model is an extension of the traditional, “flat” relational model in which relations can also have relation-valued entries. Its “default” query language, the nested algebra, is rather weak, unfortunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the polynomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed. Two polynomial-time restrictions of the fixpoint closure of the nested algebra were proposed: the restricted fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu). Here, we prove two results. First we show that both restrictions are equivalent in expressive power. The proof technique relies on known encodings of nested relations into flat ones, and on a novel technique, called type substitution, by which we reduce the equivalence of the two restrictions to its obvious counterpart in the flat relational model. Second we prove that both the bounded fixpoint queries and the restricted fixpoint queries admit normal forms, in which the fixpoint occurs exactly once. The proof technique relies on a novel encoding method of nested relations into flat ones.     

Eigenspaces of the discrete Walsh transform

We refine the notion of a discrete Walsh function and generalize the notion of a discrete Walsh transform, for which we propose a method for generating a corresponding W-matrix. We propose spectral decompositions of the discrete Walsh transform operators in arbitrary enumerations, as well as methods for finding bases of eigenspaces, one of them using a new direct product of matrices. We propose a notation for the fast discrete Walsh transform algorithm in the Paley enumeration. We construct Parseval frames for eigenspaces of the discrete Walsh transform in the Paley enumeration and demonstrate methods for applying them in error detection and correction.     

A semantical framework for supporting subjective and conditional probabilities in deductive databases

We present a theoretical basis for supporting subjective and conditional probabilities in deductive databases. We design a language that allows a user greater expressive power than classical logic programming. In particular, a user can express the fact thatA is possible (i.e.A has non-zero probability),B is possible, but (A B) as a whole is impossible. A user can also freely specify probability annotations that may contain variables. The focus of this paper is to study the semantics of programs written in such a language in relation to probability theory. Our model theory which is founded on the classical one captures the uncertainty described in a probabilistic program at the level of Herbrand interpretations. Furthermore, we develop a fixpoint theory and a proof procedure for such programs and present soundness and completeness results. Finally we characterize the relationships between probability theory and the fixpoint, model, and proof theory of our programs.     

A relationship-based approach to model integration

A key problem in model-based development is integrating a collection of models into a single, larger, specification as a way to construct a functional system, to develop a unified understanding, or to enable automated reasoning about properties of the resulting system. In this article, we suggest that the choice of a particular model integration operator depends on the inter-model relationships that hold between individual models. Based on this observation, we distinguish three key integration operators studied in the literature—merge, composition and weaving—and describe each operator along with the notion of relationship that underlies it. We then focus on the merge activity and provide a detailed look at the factors that one must consider in defining a merge operator, particularly the way in which the relationships should be captured during merge. We illustrate these factors using two merge operators that we have developed in our earlier work for combining models that originate from distributed teams.