Disjunctive LP+integrity constraints= stable model semantics

We show that stable models of logic programs may be viewed as minimal models of programs that satisfy certain additional constraints. To do so, we transform the normal programs into disjunctive logic programs and sets of integrity constraints. We show that the stable models of the normal program coincide with the minimal models of the disjunctive program thatsatisfy the integrity constraints. As a consequence, the stable model semantics can be characterized using theextended generalized closed world assumption for disjunctive logic programs. Using this result, we develop a bottomup algorithm for function-free logic programs to find all stable models of a normal program by computing the perfect models of a disjunctive stratified logic program and checking them for consistency with the integrity constraints. The integrity constraints provide a rationale as to why some normal logic programs have no stable models.     

Recognition of Simple Enlarged Horn Formulas and Simple Extended Horn Formulas

The enlarged Horn formulas generalize the extended Horn formulas introduced by Chandru and Hooker (1991). Their satisfying truth assignments can be generated with polynomial delay. Unfortunately no polynomial algorithm is known for recognizing enlarged Horn formulas or extended Horn formulas. In this paper we define the class of simple enlarged Horn formulas, a subclass of the enlarged Horn formulas, that contains the simple extended Horn formulas introduced by Swaminathan and Wagner (1995). We present recognition algorithms for the simple enlarged Horn formulas and the simple extended Horn formulas whose complexity is bounded by the complexity of the arborescence-realization problem.     

Incremental reasoning with lazy behavioral subtyping for multiple inheritance

Object-orientation supports code reuse and incremental programming. Multiple inheritance increases the possibilities for code reuse, but complicates the binding of method calls and thereby program analysis. Behavioral subtyping allows program analysis under an open world assumption; i.e., under the assumption that class hierarchies are extensible. However, method redefinition is severely restricted by behavioral subtyping, and multiple inheritance may lead to conflicting restrictions from independently designed superclasses. This paper presents a more liberal approach to incremental reasoning for multiple inheritance under an open world assumption. The approach, based on lazy behavioral subtyping, is well-suited for multiple inheritance, as it incrementally imposes context-dependent behavioral constraints on new subclasses. We first present the approach for a simple language and show how incremental reasoning can be combined with flexible code reuse. Then this language is extended with a hierarchy of interface types which is independent of the class hierarchy. In this setting, flexible code reuse can be combined with modular reasoning about external calls in the sense that each class is analyzed only once. We formalize the approach as a calculus and show soundness for both languages.     

On the Use of an Extended Relational Model to Handle Changing Incomplete Information

In this paper we consider approaches to updating databases containing null values and incomplete information. Our approach distinguishes between modeling incompletely known worlds and modeling changes in these worlds. As an alternative to the open and closed world assumptions, we propose the expanded closed world assumption. Under this assumption, we discuss how to perform updates on databases containing set nulls, marked nulls, and simple conditional tuples, and address some issues of refining incompletely specified information.     

On the computational cost of disjunctive logic programming: Propositional case

This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a propositional formula is satisfied by all models according to a given semantics. We concentrate on finite propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is ₂ ^p -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is ₂ ^p -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.Parts of the results in this paper appeared in form of an abstract in the Proceedings of the Twelfth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pp. 158–167. Other parts appeared in shortened form in the Proceedings of the International Logic Programming Symposium, Vancouver, October 1993 (ILPS-93), pp. 266–278. MIT Press.     

H 2 design of one-degree-of-freedom decoupling controllers for square plants

Decoupling design of one-degree-of-freedom controllers is treated for the generalised plant model within the H ₂ framework. The class of all realisable closed loop transfer matrices is parametrised under a mild assumption on non-unity feedback sensors. A set of compact assumptions is presented to guarantee the existence of the optimal H ₂ controller. Together with the optimal one, the class of all H ₂ controllers that yield finite H ₂ cost is obtained. The optimal closed transfer matrix and its associated controller are shown to be strictly proper under the reasonable order assumptions on the generalised plant.     

Complexity and undecidability results for logic programming

This paper surveys complexity, degree of uncomputability, and expressive power results for logic programming. Some major decision problem complexity results and other results for logic programming are also covered. It also proves several new results filling in previous gaps in the literature. The paper considers seven logic programming semantics: the van Emden-Kowalski semantics for definite (Horn) logic programs; the perfect model semantics for stratified and for locally stratified logic programs; and the two- and three-valued program completion semantics, the well-founded semantics, and the stable semantics, all for normal logic programs, under skeptical inference. The main results concern expressibility and query complexity/uncomputability in five contexts: for propositional logic programs, for first order logic programs with infinite Herbrand universes on their Herbrand universes (a closed domain assumption), for first order logic programs with infinite Herbrand universes on those universes extended with infinitely many new elements (an open domain assumption), and for logic programs without function or constant symbols evaluated over varying extensional databases (DATALOG-type results, data complexity results only) under both closed and open domain assumptions. Several of the open domain assumption results are new to this paper. Other results surveyed are (1) results about the family of all stable models of a program and (2) decision questions about when a logic program has nice properties with respect to a semantics (e.g., a unique stable model). One decision result, for well-founded semantics, is new to this paper.Work supported in part by NSF grant IRI-8905166.     

Relaxing the homogeneity assumption in usability testing

Much attention has been paid to the question of how many subjects are needed in usability research. Virzi (1992) modelled the accumulation of usability problems with increasing numbers of subjects and claimed that five subjects are sufficient to find most problems. The current paper argues that this answer is based on an important assumption, namely that all types of users have the same probability of encountering all usability problems. If this homogeneity assumption is violated, then more subjects are needed. A modified version of Virzi's model demonstrates that the number of subjects required increases with the number of heterogeneous groups. The model also shows that the more distinctive the groups, the more subjects will be required. This paper will argue that the simple answer 'five' cannot be applied in all circumstances. It most readily applies when the probability that a user will encounter a problem is both high and similar for all users. It also only applies to simple usability tests that seek to detect the presence, but not the statistical prevalence, of usability problems.     

Displacement structure approach to discrete-trigonometric-transform based preconditioners of G.Strang type and of T.Chan type

In this paper adisplacement structure technique is used to design a class of newpreconditioners for theconjugate gradient method applied to the solution of large Toeplitz linear equations. Explicit formulas are suggested for the G.Strang-type and for the T.Chan-type preconditioners belonging to any of 8 classes of matrices diagonalized by the correspondingdiscrete cosine or sine transforms. Under the standard Wiener class assumption theclustering property is established for all of these preconditioners, guaranteeing a rapid convergence of the preconditioned conjugate gradient method. The formulas for the G.Strang-type preconditioners have another important application: they suggest a wide variety of newO(m logm) algorithms for multiplication of a Toeplitz matrix by a vector, based on any of the 8 DCT’s and DST’s. Recentlytransformations of Toeplitz matrices to Vandermonde-like or Cauchy-like matrices have been found to be useful in developing accuratedirect methods for Toeplitz linear equations. Here it is suggested to further extend the range of the transformation approach by exploring it foriterative methods; this technique allowed us to reduce the complexity of each iteration of the preconditioned conjugate gradient method to 4 discrete transforms per iteration. This work was supported in part by ARO contract DAAH04-96-1-0176, NSF contract CCR-962811 and also by DARPA contract F49620-95-1-0525. The views and conclusions contained in these documents are those of the author(s) and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the National Science Foundation, the Advanced Research Projects Agency, the Army Research office, or the U.S. Government.     

Histograms as statistical estimators for aggregate queries

The traditional statistical assumption for interpreting histograms and justifying approximate query processing methods based on them is that all elements in a bucket have the same frequency—this is called uniform distribution assumption. In this paper, we analyze histograms from a statistical point of view. We show that a significantly less restrictive statistical assumption – the elements within a bucket are randomly arranged even though they might have different frequencies – leads to identical formulas for approximating aggregate queries using histograms. Under this assumption, we analyze the behavior of both unidimensional and multidimensional histograms and provide tight error guarantees for the quality of approximations. We conclude that histograms are the best estimators if the assumption holds; sampling and sketching are significantly worse. As an example of how the statistical theory of histograms can be extended, we show how XSketches – an approximation technique for XML queries that uses histograms as building blocks – can be statistically analyzed. The combination of the random shuffling assumption and the other statistical assumptions associated with XSketch estimators ensures a complete statistical model and error analysis for XSketches.     

Alcune formule per il calcolo numerico della transformata di Fourier

In this paper we get three formulas to compute Fourier integral. The formulas are essentially a linear combination of values of the functionf(t) with weight coefficients, which are independent of thef(t) and of the parameter ω. The formulas are obtained by means of a polinomial approximation off(t) on each interval (kmτ, (k+1)mτ) wherem is an integer and τ is the period of the trigonometric function.      

Belief revision within fragments of propositional logic

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. Here we present a general approach to define new revision operators derived from known operators, such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual Horn, Krom and affine formulas, as well.     

一类一阶逻辑公式中的公理化真度理论及其应用

设Φ是全体不含函数符号的一阶闭逻辑公式之集.本文基于有限模型和均匀概率的思想对非单调逻辑中的典型案例做了分析,通过概率计算给出了应当赋予文字的完全闭包及其合取的真度值.以此为基础,在Φ中建立了公理化的真度理论.证明了Φ中每个公式的真度都是可计算的,并且证明了Φ中逻辑公式的真度之集H与命题逻辑中的计算结果相一致,特别是其中所有闭文字的真度都等于1/2.在真度理论的基础上引入了Φ中公式之间相似度和伪距离的计算方法,并提出了逻辑理论的相容度理论.作为应用,给出了估计Horn子句型数据库相容度的一种方法.     

Information loss in knowledge compilation: A comparison of Boolean envelopes

Since Selman and Kautz's seminal work on the use of Horn approximation to speed up the querying of knowledge bases, there has been great interest in Boolean approximation for AI applications. There are several Boolean classes with desirable computational properties similar to those of the Horn class. The class of affine Boolean functions, for example, has been proposed as an interesting alternative to Horn for knowledge compilation. To investigate the trade-offs between precision and efficiency in knowledge compilation, we compare, analytically and empirically, four well-known Boolean classes, and their combinations, for ability to preserve information. We note that traditional evaluation which explores unit-clause consequences of random hard 3-CNF formulas does not tell the full story, and we complement that evaluation with experiments based on a variety of assumptions about queries and the underlying knowledge base.     

On renamable Horn and generalized Horn functions

A Boolean function in disjunctive normal form (DNF) is aHorn function if each of its elementary conjunctions involves at most one complemented variable. Ageneralized Horn function is constructed from a Horn function by disjuncting a nested set of complemented variables to it. The satisfiability problem is solvable in polynomial time for both Horn and generalized Horn functions. A Boolean function in DNF is said to berenamable Horn if it is Horn after complementation of some variables. Succinct mathematical characterizations and linear-time algorithms for recognizing renamable Horn and generalized Horn functions are given in this paper. The algorithm for recognizing renamable Horn functions gives a new method to test 2-SAT. Some computational results are also given.The authors were supported in part by the Office of Naval Research under University Research Initiative grant number N00014-86-K-0689. Chandru was also supported by NSF grant number DMC 88-07550.The authors gratefully acknowledge the partial support of NSF (Grant DMS 89-06870) and AFOSR (Grant 89-0066 and 89-0512).     

Default theories over monadic languages

In this paper we compare the semantical and syntactical definitions of extensions for open default theories. We prove that, over monadic languages, these definitions are equivalent and do not depend on the cardinality of the underlying infinite world. We also show that, under the domain closure assumption, one free variable open default theories are decidable.     

Double Horn Functions

In this paper, we define double Horn functions, which are the Boolean functionsfsuch that bothfand its complement (i.e., negation)fare Horn, and investigate their semantical and computational properties. Double Horn functions embody a balanced treatment of positive and negative information in the course of the extension problem of partially defined Boolean functions (pdBfs), where a pdBf is a pair (T, F) of disjoint setsT, F⊆{0, 1}ⁿof true and false vectors, respectively, and an extension of (T, F) is a Boolean functionfthat is compatible withTandF. We derive syntactic and semantic characterizations of double Horn functions, and determine the number of such functions. The characterizations are then exploited to give polynomial time algorithms (i) that recognize double Horn functions from Horn DNFs (disjunctive normal forms), and (ii) that compute the prime DNF from an arbitrary formula, as well as its complement and its dual. Furthermore, we consider the problem of determining a double Horn extension of a given pdBf. We describe a polynomial time algorithm for this problem and moreover an algorithm that enumerates all double Horn extensions of a pdBf with polynomial delay. However, finding a shortest double Horn extension (in terms of the size of a formula?representing it) is shown to be intractable.