A compact fixpoint semantics for term rewriting systems

This work is motivated by the fact that a “compact” semantics for term rewriting systems, which is essential for the development of effective semantics-based program manipulation tools (e.g. automatic program analyzers and debuggers), does not exist. The big-step rewriting semantics that is most commonly considered in functional programming is the set of values/normal forms that the program is able to compute for any input expression. Such a big-step semantics is unnecessarily oversized, as it contains many “semantically useless” elements that can be retrieved from a smaller set of terms. Therefore, in this article, we present a compressed, goal-independent collecting fixpoint semantics that contains the smallest set of terms that are sufficient to describe, by semantic closure, all possible rewritings. We prove soundness and completeness under ascertained conditions. The compactness of the semantics makes it suitable for applications. Actually, our semantics can be finite whereas the big-step semantics is generally not, and even when both semantics are infinite, the fixpoint computation of our semantics produces fewer elements at each step. To support this claim we report several experiments performed with a prototypical implementation.     

Bottom-up Evaluation of Datalog with Negation

Declarative semantics gives the meaning of a logic program in terms of properties,while the procedural semantics gives the meaning in terms of the execution or evaluation of the program.From the database point of view,the procedural semantics of the program is equally important.This paper focuses on the study of the bottom-up evaluation of the WFM semantics of datalog‘ programs.To compute the WFM,first,the stability transformation is revisited,and a new operator Op and its fixpoint are defined. Based on this,a fixpoint semantics,called oscillating fixpoint model semantics,is defined.Then,it is shown that for any datalog‘ program the oscillating fixpoint model is identical to its WFM.So,the oscillating fixpoint model can be viewed as an alternative (constructive) definition of WFM.The underlying operation (or transformation) for reaching the oscillating fixpoint provides a potential of bottom-up evaluation.For the sake of computational feasibility,the strongly range-restricted program is considered,and an algorithm used to compute the oscillating fixpoint is described.     

Probabilistic knowledge bases

We define a new fixpoint semantics for rule based reasoning in the presence of weighted information. The semantics is illustrated on a real world application requiring such reasoning. Optimizations and approximations of the semantics are shown so as to make the semantics amenable to very large scale real world applications. We finally prove that the semantics is probabilistic and reduces to the usual fixpoint semantics of stratified Datalog if all information is certain. We implemented various knowledge discovery systems which automatically generate such probabilistic decision rules. In collaboration with a bank in Hong Kong we use one such system to forecast currency exchange rates     

描述逻辑FL-循环术语集的语义及推理

循环术语集是描述逻辑长期以来的研究难点,它的最基本的问题即语义及推理问题没有得到合理的解决.文中分析了描述逻辑循环术语集的研究现状和存在的问题,在Baader的基础上进一步研究了描述逻辑FL~-循环术语集的语义及推理问题.给出了FL~-循环术语集的语法、语义和不动点模型的构造方法.针对FL~-循环术语集的需要,提出了一种新的有限自动机,使用有限自动机给出了不动点语义和描述语义下FL~-循环术语集的可满足性和包含推理算法,证明了推理算法的正确性,并给出了推理算法的复杂性定理.     

Logical approximation for program analysis

The abstract interpretation of programs relates the exact semantics of a programming language to a finite approximation of those semantics. In this article, we describe an approach to abstract interpretation that is based in logic and logic programming. Our approach consists of faithfully representing a transition system within logic and then manipulating this initial specification to create a logical approximation of the original specification. The objective is to derive a logical approximation that can be interpreted as a terminating forward-chaining logic program; this ensures that the approximation is finite and that, furthermore, an appropriate logic programming interpreter can implement the derived approximation. We are particularly interested in the specification of the operational semantics of programming languages in ordered logic, a technique we call substructural operational semantics (SSOS). We show that manifestly sound control flow and alias analyses can be derived as logical approximations of the substructural operational semantics of relevant languages.     

A semantics for a class of non-deterministic and causal production system programs

We define a class of function-free rule-based production system (PS) programs that exhibit non-deterministic and/or causal behavior. We develop a fixpoint semantics and an equivalent declarative semantics for these programs. The criterion to recognize the class of non-deterministic causal (NDC) PS programs is based upon extending and relaxing the concept of stratification, to partition the rules of the program. Unlike strict stratification, this relaxed stratification criterion allows a more flexible partitioning of the rules and admits programs whose execution is non-deterministic or causal or both. The fixpoint semantics is based upon a monotonic fixpoint operator which guarantees that the execution of the program will terminate. Each fixpoint corresponds to a minimal database of answers for the NDC PS program. Since the execution of the program is non-deterministic, several fixpoints may be obtained. To obtain a declarative meaning for the PS program, we associate a normal logic program with each NDC PS program. We use the generalized disjunctive well-founded semantics to provide a meaning to the normal logic program Through these semantics, a well-founded state is associated with and a set of possible extensions, each of which are minimal models for the well-founded state, are obtained. We show that the fixpoint semantics for the NDC PS programs is sound and complete with respect to the declarative semantics for the corresponding normal logic program .This research is partially sponsored by the National Science Foundation under grant IRI-9008208 and by the Institute for Advanced Computer Studies.     

Improving the results of program analysis by abstract interpretation beyond the decreasing sequence

The classical method for program analysis by abstract interpretation consists in computing first an increasing sequence using an extrapolation operation, called widening, to correctly approximate the limit of the sequence. Then, this approximation is improved by computing a decreasing sequence without widening, the terms of which are all correct, more and more precise approximations. It is generally admitted that, when the decreasing sequence reaches a fixpoint, it cannot be improved further. As a consequence, most efforts for improving the precision of an analysis have been devoted to improving the limit of the increasing sequence. In a previous paper, we proposed a method to improve a fixpoint after its computation. This method consists in computing from the obtained solution a new starting value from which increasing and decreasing sequences are computed again. The new starting value is obtained by projecting the solution onto well-chosen components. The present paper extends and improves the previous paper: the method is discussed in view of some example programs for which it fails. A new method is proposed to choose the restarting value: the restarting value is no longer a simple projection, but is built by gathering and combining information backward the widening nodes in the basic solution. Experiments show that the new method properly solves all our examples, and improves significantly the results obtained on a classical benchmark.     

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.     

基于抽象解释的Prolog程序验证技术研究

作为一种通用的语义近似理论,抽象解释已广泛应用于各类程序的形式化验证中.现有基于抽象解释的逻辑程序验证技术未涉及与程序点相关联的程序性质的验证,设计能够描述此类性质的逻辑程序具体语义和抽象语义是构造相应验证工具的关键.本文给出了一种基于抽象解释的Prolog程序验证方法,该方法采用了具有路径信息的Prolog语义及其抽象作为语义基础,因而可用于验证与程序点相关联的程序特性.本文例子表明了该验证方法的有效性.     

A fixpoint semantics of Horn sentences based on substitution sets

The formal semantics of a given Horn sentence is usually defined as a set of ground atoms, which is really the minimal Herbrand interpretation of the Horn sentence, by both model-theoretic and fixpoint approaches. In the present paper, we propose another denotational semantics of a Horn sentence, denoting the set of substitutions with which atoms are derivable by unit deduction from the Horn sentence to get a direct correspondence between the semantics of the Horn sentence and the answer set concerned with its computation, and give denotational semantics even when the Horn sentence is unsatisfiable. In accordance with the unit deductions from a Horn sentence, we define a continuous function from a direct product of powersets of a substitution set to itself, and regard the least fixpoint of the function as the semantics, which can provide the answer set for computations of the Horn sentence.     

Lower and upper bounds in zone-based abstractions of timed automata

Timed automata have an infinite semantics. For verification purposes, one usually uses zone-based abstractions w.r.t. the maximal constants to which clocks of the timed automaton are compared. We show that by distinguishing maximal lower and upper bounds, significantly coarser abstractions can be obtained. We show soundness and completeness of the new abstractions w.r.t. reachability and demonstrate how information about lower and upper bounds can be used to optimise the algorithm for bringing a difference bound matrix into normal form. Finally, we experimentally demonstrate that the new techniques dramatically increase the scalability of the real-time model checker UPPAAL.     

The Least Fixpoint Transformation for Disjunctive Logic Programs

The paradigm of disjunctive logic programming(DLP)enhances greatly the expressive power of normal logic programming(NLP)and many(declarative)semantics have been defined for DLP to cope with various problems of knowledge representation in artificial intelligence.However,the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored.This paper defines an immediate consequence operatro T^GP for each disjunctive program and shows that T^GP has the least and computable fixpoint Lft(P),Lft is,in fact,a program transformation for DLP,which transforms all disjunctive programs into negative programs.It is shown that Lft preserves many key semantics,including the disjunctive stable models,well-founded model,disjunctive argunent semantics DAS,three-valued models,ect.Thic means that every disjunctive program P has a unique canonical form Lft(P)with respect to these semantics.As a result,the work in this paper provides a unifying framework for studying the expressive ability of various semantics for DLP On the other hand,the computing of the above semantics for negative programs is ust a trivial task,therefore,Lft(P)is also an optimization method for DLP.Another application of Lft is to derive some interesting semantic results for DLP.     

Contributions to the semantics of logic perpetual processes

Summary Logic perpetual processes (logic programs with infinite data structures) have been given several formal (operational and fixpoint) semantics. In this paper, we compare the various semantics and define a formal characterization of a least fixpoint semantics, which is based on a modified version of the logic programs and which is satisfactory for a large class of logical perpetual processes. Our results show that all the proposed fixpoint semantics are not equivalent to the operational semantics and suggest an improvement of the least fixpoint approach.     

Instruction-level security typing by abstract interpretation

We present a method based on abstract interpretation to check secure information flow in programs with dynamic structures where input and output channels are associated with security levels. In the concrete operational semantics each value is annotated by a security level dynamically taking into account both the explicit and the implicit information flows. We define a collecting semantics which associates with each program point the set of concrete states of the machine when the point is reached. The abstract domains are obtained from the concrete ones by keeping the security levels and forgetting the actual values. Using this framework, we define an abstract semantics, called instruction-level security typing, that allows us to certify a larger set of programs with respect to the typing approaches to check secure information flow. An efficient implementation is shown, operating a fixpoint iteration similar to that of the Java bytecode verification. This work was partially supported by the Italian COFIN 2004 project “AIDA: Abstract Interpretation Design and Application”.     

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.     

Generalized disjunctive well-founded semantics for logic programs

Generalized disjunctive well-founded semantics (GDWFS) is a refined form of the generalized well-founded semantics (GWFS) of Baral, Lobo and Minker, to disjunctive logic programs. We describe fixpoint, model theoretic and procedural characterizations of GDWFS and show their equivalence. The fixpoint semantics is similar to the fixpoint semantics of the GWFS, except that it iterates over state-pairs (a pair of sets; one a set of disjunctions of atoms and the other a pair of conjunctions of atoms), rather than partial interpretations. The model theoretic semantics is based on a dynamic stratification of the program. The procedural semantics is based on SLIS refutations, + trees and SLISNF trees.     

Abstract Interpretation for Proving Secrecy Properties in Security Protocols

A cryptographic protocol is a distributed program that can be executed by several actors. Since several runs of the protocol within the same execution are allowed, models of cryptoprotocols are often infinite. Sometimes, for verification purposes, only a finite and approximated model is needed. For this, we consider the problem of computing such an approximation and we propose to simulate the required partial execution in an abstract level. More precisely, we define an abstract finite category G ^a as an abstract game semantics for the SPC calculus, a dedicated calculus for security protocols. The abstract semantics is then used to build a decision procedure for secrecy correctness in security protocols.     

Coherence approach to logic program revision

In this paper, we present a new approach to the problem of revising extended programs; we base this approach on the coherence theory initially advocated by Gardenfors for belief revision. Our approach resolves contradiction by removing only conflicting information, not the believed source of it, and therefore, keeps information loss minimal. Furthermore, since there is no need to search for problematic assumptions, as is done in the traditional assumption-removal approach, our approach provides a skeptical revision semantics that is tractable. We define the skeptical and credulous coherence semantics and show that both semantics can be characterized in terms of the fixpoint semantics of a revised program using a simple program-revision technique. These semantics provide a suitable framework for knowledge and belief revision in the context of logic programs. Semantical properties and advantages of the proposed revision semantics are also analyzed     

Acceleration of the abstract fixpoint computation in numerical program analysis

Static analysis by abstract interpretation aims at automatically proving properties of computer programs, by computing invariants that over-approximate the program behaviors. These invariants are defined as the least fixpoint of a system of semantic equations and are most often computed using the Kleene iteration. This computation may not terminate so specific solutions were proposed to deal with this issue. Most of the proposed methods sacrifice the precision of the solution to guarantee the termination of the computation in a finite number of iterations. In this article, we define a new method which allows to obtain a precise fixpoint in a short time. The main idea is to use numerical methods designed for accelerating the convergence of numerical sequences. These methods were primarily designed to transform a convergent, real valued sequence into another sequence that converges faster to the same limit. In this article, we show how they can be integrated into the Kleene iteration in order to improve the fixpoint computation in the abstract interpretation framework. An interesting feature of our method is that it remains very close to the Kleene iteration and thus can be easily implemented in existing static analyzers. We describe a general framework and its application to two numerical abstract domains: the interval domain and the octagon domain. Experimental results show that the number of iterations and the time needed to compute the fixpoint undergo a significant reduction compared to the Kleene iteration, while its precision is preserved.     

目标独立的Prolog程序路径依赖分析语义

在Prolog程序分析中,考虑程序的执行路径和非逻辑的cut操作可提高程序分析的精度.当前用于Prolog程序路径依赖分析的语义因依赖于程序执行的目标而不适合目标独立的程序分析.为此,本文采用了一种携带路径信息并允许cut操作的Prolog抽象语法,在此基础上给出了Prolog的操作语义和一种目标独立的标号树(LT)语文,并证明了LT语义相对于操作语义的正确性.LT语义可作为目标独立的Prolog程序路径依赖分析的基础.