基于逻辑程序的访问控制描述与推理

提出访问控制的逻辑描述方法,满足最小模型语义的条件(不含负逻辑),并分析访问控制逻辑程序中不动点的迭代计算方法。通过迭代计算,得到访问控制逻辑程序的最小Herbrand模型——Mp。使用基于逻辑程序的方法对访问控制策略进行了较为精确的推理。     

Foundation of logic programming based on inductive definition

A logical system of inference rules intended to give the foundation of logic programs is presented. The distinguished point of the approach taken here is the application of the theory of inductive definitions, which allows us to uniformly treat various kinds of induction schema and also allows us to regardnegation as failure as a kind of induction schema. This approach corresponds to the so-called least fixpoint semantics. Moreover, in our formalism, logic programs are extended so that a condition of a clause may be any first-order formula. This makes it possible to write a quantified specification as a logic program. It also makes the class of induction schemata much larger to include the usual course-of-values inductions.     

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.     

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.     

Formalization of correctness of recursive definitions

We use the fixpoint approach to formalize the correctness of recursive definitions within the framework of first-order predicate calculus. Although the least fixpoint semantics is used, our results suggest some general methods of proving the correctness of recursive definitions without knowing their least fixpoints explicitly.     

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.     

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.     

可更新Datalog的分布式时态逻辑扩展及应用

针对现有的分布式逻辑语言缺乏完整时态表达力等问题,将分布式时态逻辑谓词引入Datalog规则,提出TU-Datalog语言。该语言通过融入U-Datalog的非即时性更新语义,形成完全声明式具有强大时态表达力的逻辑编程语言和环境。通过扩展U-Datalog逻辑固定点语义,提出TU-Datalog语言的固定点时态演化规则,并对该语言的语法、语义、评价算法进行了研究,最后对该语言的应用做了说明和示例。     

Weak Generalized Closed World Assumption

Explicit representation of negative information in logic programs is not feasible in many applications such as deductive databases and artificial intelligence. Defining default rules which allow implicit inference of negated facts from positive information encoded in a logic program has been an attractive alternative to the explicit representation approach. There is, however, a difficulty associated with implicit default rules. Default rules such as the CWA and the GCWA, which closely model logical negation, are in general computationally intractable. This has led to the development of weaker definitions of negation such as the Negation-As-Failure (NF) and the Support-For-Negation (SN) rules which are computationally simpler. These are sound implementations of the CWA and the GCWA, respectively. In this paper, we define an alternative rule of negation based upon the fixpoint definition of the GCWA. This rule, called the Weak Generalized Closed World Assumption (WGCWA), is a weaker definition of the GCWA that allows us to implement a sound negation rule, called the Negation-As-Finite-Failure (NAFF), similar to the NF-rule and less cumbersome than the SN-rule. We present three definitions of the NAFF. Two declarative definitions similar to those for the NF-rule and one procedural definition based on SLI-resolution.     

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.     

RGITL: A temporal logic framework for compositional reasoning about interleaved programs

This paper gives a self-contained presentation of the temporal logic Rely-Guarantee Interval Temporal Logic (RGITL). The logic is based on interval temporal logic (ITL) and higher-order logic. It extends ITL with explicit interleaved programs and recursive procedures. Deduction is based on the principles of symbolic execution and induction, known from the verification of sequential programs, which are transferred to a concurrent setting with temporal logic. We include an interleaving operator with compositional semantics. As a consequence, the calculus permits proving decomposition theorems which reduce reasoning about an interleaved program to reasoning about individual threads. A central instance of such theorems are rely-guarantee (RG) rules, which decompose global safety properties. We show how the correctness of such rules can be formally derived in the calculus. Decomposition theorems for other global properties are also derivable, as we show for the important progress property of lock-freedom. RGITL is implemented in the interactive verification environment KIV. It has been used to mechanize various proofs of concurrent algorithms, mainly in the area oflinearizable and lock-free algorithms.     

Deriving constraints among argument sizes in logic programs

In a logic program the feasible argument sizes of derivable facts involving ann-ary predicate are viewed as a set of points in the positive orthant of ⁿ . We investigate a method of deriving constraints on the feasible set in the form of a polyhedral convex set in the positive orthant, which we call apolycone. Faces of this polycone represent inequalities proven to hold among the argument sizes. These inequalities are often useful for selecting an evaluation method that is guaranteed to terminate for a given logic procedure. The methods may be applicable to other languages in which the sizes of data structures can be determined syntactically.For any atomic formula (atom, for short) in a rule, we show how to express the vector of its argument sizes as a system of linear equations and inequalities involving sizes of the logical variables that occur in it. This system defines a polycone, which represents the set offeasible argument size vectors. Transformations combine polycones for all atoms in one rule to give the feasible polycone for the entire rule.We introduce ageneralized Tucker representation for systems of linear equations. We prove that every polycone has a uniquenormal form in this representation, and give an algorithm to produce it. This in turn gives a decision procedure for the question of whether two sets of linear equations define the same polycone.When a predicate has several rules, the union of the individual rule's polycones gives the set of feasible argument size vectors for the predicate. Because this set is not necessarily convex, we instead operate with the smallest enclosing polycone, which is the closure of the convex hull of the union. Retaining convexity is one of the key features of our technique.Recursion is handled by finding a polycone that is a fixpoint of a transformation that is derived from both the recursive and nonrecursive rules. Some methods for finding a fixpoint are presented, but there are many unresolved problems in this area.An extended abstract of this paper appeared in9th ACM Symposium on Principles of Database Systems, March 1990.     

Logic programming with solution preferences

Preference logic programming (PLP) is an extension of logic programming for declaratively specifying problems requiring optimization or comparison and selection among alternative solutions to a query. PLP essentially separates the programming of a problem itself from the criteria specification of its solution selection. In this paper we present a declarative method for specifying preference logic programs. The method introduces a precise formalization for the syntax and semantics of PLP. The syntax of a preference logic program contains two disjoint sets of definite clauses, separating a core program specifying a general computational problem from its preference rules for optimization; the semantics of PLP is given based on the Herbrand model and fixed point theory, where how preferences affects the least Herbrand model of a logic program is interpreted as a sequence of meta-level mapping operations. In addition, we present an operational semantics based on a new resolution strategy and a memoized recursive algorithm for computing strictly stratified logic programs with well-formed preferences, and further show that the operational semantics of such a preference logic program is consistent to its declarative semantics.     

Non-determinism in logic-based languages

The use of non-determinism in logic-based languages is motivated using pragmatic and theoretical considerations. Non-deterministic database queries and updates occur naturally, and there exist non-deterministic implementations of various languages. It is shown that non-determinism resolves some difficulties concerning the expressive power of deterministic languages: there are non-deterministic languages expressing low complexity classes of queries/updates, whereas no such deterministic languages are known. Various mechanisms yielding non-determinism are reviewed. The focus is on two closely related families of non-deterministic languages. The first consists of extensions of Datalog with negations in bodies and/or heads of rules, with non-deterministic fixpoint semantics. The second consists of non-deterministic extensions of first-order logic and fixpoint logics, using thewitness operator. The expressive power of the languages is characterized. In particular, languages expressing exactly the (deterministic and non-deterministic) queries/updates computable in polynomial time are exhibited, whereas it is conjectured that no analogous deterministic language exists. The connection between non-deterministic languages and determinism is also explored. Several problems of practical interest are examined, such as checking (statically or dynamically) if a given program is deterministic, detecting coincidence of deterministic and non-deterministic semantics, and verifying termination for non-deterministic programs.Work supported by the Projet de Recherche Coordonnée BD3.Work supported in part by the National Science Foundation under grants IRI-8816078 and INT-8817874. The work was done in part while the author was visiting INRIA.     

An automata theoretic decision procedure for the propositional mu-calculus

The propositional mu-calculus is a propositional logic of programs which incorporates a least fixpoint operator and subsumes the propositional dynamic logic of Fischer and Ladner, the infinite looping construct of Streett, and the game logic of Parikh. We give an elementary time decision procedure, using a reduction to the emptiness problem for automata on infinite trees. A small model theorem is obtained as a corollary.     

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 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.     

The addition of bounded quantification and partial functions to a computational logic and its theorem prover

We describe an extension to our quantifier-free computational logic to provide the expressive power and convenience of bounded quantifiers and partial functions. By quantifier we mean a formal construct which introduces a bound or indicial variable whose scope is some subexpression of the quantifier expression. A familiar quantifier is the Σ operator which sums the values of an expression over some range of values on the bound variable. Our method is to represent expressions of the logic as objects in the logic, to define an interpreter for such expressions as a function in the logic, and then define quantifiers as ‘mapping functions’. The novelty of our approach lies in the formalization of the interpreter and its interaction with the underlying logic. Our method has several advantages over other formal systems that provide quantifiers and partial functions in a logical setting. The most important advantage is that proofs not involving quantification or partial recursive functions are not complicated by such notions as ‘capturing’, ‘bottom’, or ‘continuity’. Naturally enough, our formalization of the partial functions is nonconstructive. The theorem prover for the logic has been modified to support these new features. We describe the modifications. The system has proved many theorems that could not previously be stated in our logic. Among them are:

? classic quantifier manipulation theorems, such as $$\sum\limits_{{\text{l}} = 0}^{\text{n}} {{\text{g}}({\text{l}}) + {\text{h(l) = }}} \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{g}}({\text{l}})} + \sum\limits_{{\text{l = }}0}^{\text{n}} {{\text{h(l)}};} $$

? elementary theorems involving quantifiers, such as the Binomial Theorem: $$(a + b)^{\text{n}} = \sum\limits_{{\text{l = }}0}^{\text{n}} {\left( {_{\text{i}}^{\text{n}} } \right)} \user2{ }{\text{a}}^{\text{l}} {\text{b}}^{{\text{n - l}}} ;$$

? elementary theorems about ‘mapping functions’ such as: $$(FOLDR\user2{ }'PLUS\user2{ O L) = }\sum\limits_{{\text{i}} \in {\text{L}}}^{} {{\text{i}};} $$

? termination properties of many partial recursive functions such as the fact that an application of the partial function described by $$\begin{gathered} (LEN X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F ({\rm E}QUAL X NIL) \hfill \\ {\rm O} \hfill \\ (ADD1 (LEN (CDR X)))) \hfill \\ \end{gathered} $$ terminates if and only if the argument ends in NIL;

? theorems about functions satisfying unusual recurrence equations such as the 91-function and the following list reverse function: $$\begin{gathered} (RV X) \hfill \\ \Leftarrow \hfill \\ ({\rm I}F (AND (LISTP X) (LISTP (CDR X))) \hfill \\ (CONS (CAR (RV (CDR X))) \hfill \\ (RV (CONS (CAR X) \hfill \\ (RV (CDR (RV (CDR X))))))) \hfill \\ X). \hfill \\ \end{gathered} $$

     

Frame rule for mutually recursive procedures manipulating pointers

Using a predicate transformer semantics of programs, we introduce statements for heap operations and separation logic operators for specifying programs that manipulate pointers. We prove a powerful Hoare total correctness rule for mutually recursive procedures manipulating pointers. The rule combines earlier proof rules for (mutually) recursive procedures with the frame rule for pointer programs. The theory, including the proofs, is implemented in the theorem prover PVS. In this implementation program variables and addresses can store values of almost any type of the theorem prover.     

On the existence of optimal fixpoints

The concept of optimal fixpoint was introduced by Manna and Shamir [6, 7] in order to extract the maximum amount of “useful” information from a recursive definition. In this paper, we extend the concept of optimal fixpoint to arbitrary posets and investigate conditions which guarantee their existence. We prove that if a poset is chain-complete and has bounded joins, then every monotonic function has an optimal fixpoint. We also provide a sort of converse which generalizes a Theorem of A. Davis [2]. If a lower semilattice has bounded joins and every monotonic function has a fixpoint, then it is chain-complete.