Optimal models of disjunctive logic programs: semantics, complexity, and computation

Almost all semantics for logic programs with negation identify a set, SEM(P), of models of program P, as the intended semantics of P, and any model M in this class is considered a possible meaning of P with regard to the semantics the user has in mind. Thus, for example, in the case of stable models [M. Gelfond et al., (1988)], choice models [D. Sacca et al., (1990)], answer sets [M. Gelfond et al., (1991)], etc., different possible models correspond to different ways of "completing" the incomplete information in the logic program. However, different end-users may have different ideas on which of these different models in SEM(P) is a reasonable one from their point of view. For instance, given SEM(P), user U/sub 1/ may prefer model M/sub 1//spl isin/SEM(P) to model M/sub 2//spl isin/SEM(P) based on some evaluation criterion that she has. We develop a logic program semantics based on optimal models. This semantics does not add yet another semantics to the logic programming arena - it takes as input an existing semantics SEM(P) and a user-specified objective function Obj, and yields a new semantics Opt(P)_/spl sube/ SEM(P) that realizes the objective function within the framework of preferred models identified already by SEM(P). Thus, the user who may or may not know anything about logic programming has considerable flexibility in making the system reflect her own objectives by building "on top" of existing semantics known to the system. In addition to the declarative semantics, we provide a complete complexity analysis and algorithms to compute optimal models under varied conditions when SEM(P) is the stable model semantics, the minimal models semantics, and the all-models semantics.     

Particle computation: complexity,algorithms, and logic

Natural Computing - We investigate algorithmic control of a large swarm of mobile particles (such as robots, sensors, or building material) that move in a 2D workspace using a global input signal...     

Direct routing: Algorithms and complexity

Direct routing is the special case ofbufferless routing whereN packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct routing:

Propositional lower bounds: Algorithms and complexity

Propositional greatest lower bounds (GLBs) are logically‐defined approximations of a knowledge base. They were defined in the context of Knowledge Compilation, a technique developed for addressing high computational cost of logical inference. A GLB allows for polynomial‐time complete on‐line reasoning, although soundness is not guaranteed. In this paper we propose new algorithms for the generation of a GLB. Furthermore, we give precise characterization of the computational complexity of the problem of generating such lower bounds, thus addressing in a formal way the question “how many queries are needed to amortize the overhead of compilation?”     

Arithmetical hierarchy and complexity of computation

Various sets of Turing machines naturally occuring in the theory of computational complexity are shown to be complete on the respective levels of the arithmetical hierarchy. Results saying that various assertions concerning computational complexity (e.g. some relativizations of the P = NP problem) are independent of formal systems like set theory are obtained as corollaries. Provable complexity classes are also investigated.     

The complexity of analog computation

We ask if analog computers can solve NP-complete problems efficiently. Regarding this as unlikely, we formulate a strong version of Church's Thesis: that any analog computer can be simulated efficiently (in polynomial time) by a digital computer. From this assumption and the assumption that P ≠ NP we can draw conclusions about the operation of physical devices used for computation.An NP-complete problem, 3-sat, is reduced to the problem of checking whether a feasible point is a local optimum of an optimization problem. A mechanical device is proposed for the solution of this problem. It encodes variables as shaft angles and uses gears and smooth cams. If we grant Strong Church's Thesis, that P ≠ NP, and a certain “Downhill Principle” governing the physical behavior of the machine, we conclude that it cannot operate successfully while using only polynomial resources.We next prove Strong Church's Thesis for a class of analog computers described by well-behaved ordinary differential equations, which we can take as representing part of classical mechanics.We conclude with a comment on the recently discovered connection between spin glasses and combinatorial optimization.     

Space complexity in on-line computation

A technique is developed for determining space complexity in on-line computation. It is shown that each of the following functions requires linear space: (i) the conversion of binary numbers into ternary numbers, (ii) the multiplication of integers and (iii) the translation of arithmetic expressions in infix notation into Polish notation.     

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.     

Deterministic propositional dynamic logic: Finite models,complexity, and completeness

Let p be a formula in deterministic propositional dynamic logic. A decision procedure for the satisfiability of p is given along with a construction of a finite model for every satisfiable p. The decision procedure runs in deterministic time 2^cn and the size of the model is bounded by n² · 4ⁿ, where n is the length of p. Finally, a complete axiomatization for deterministic propositional dynamic logic is given, based on the Segerberg axoms for propositional dynamic logic.     

Algorithms and analyses for maximal vector computation

The maximal vector problem is to identify the maximals over a collection of vectors. This arises in many contexts and, as such, has been well studied.The problem recently gained renewed attention with skyline queries for relational databases and with work to develop skyline algorithms that are external and relationally well behaved. While many algorithms have been proposed, how they perform has been unclear. We study the performance of, and design choices behind, these algorithms. We prove runtime bounds based on the number of vectors N and the dimensionality K. Early algorithms based on divide and conquer established seemingly good average and worst-case asymptotic runtimes. In fact, the problem can be solved in average-case (holding K as fixed). We prove, however, that the performance is quite bad with respect to K. We demonstrate that the more recent skyline algorithms are better behaved, and can also achieve average-case. While K matters for these, in practice, its effect vanishes in the asymptotic. We introduce a new external algorithm, LESS, that is more efficient and better behaved. We evaluate LESS’s effectiveness and improvement over the field, and prove that its average-case running time is .Part of this work was conducted at William & Mary where Ryan Shipley was a student and Parke Godfrey was on faculty while on leave of absence from York.     

Algorithms and complexity results for persuasive argumentation

The study of arguments as abstract entities and their interaction as introduced by Dung (1995) [1] has become one of the most active research branches within Artificial Intelligence and Reasoning. A main issue for abstract argumentation systems is the selection of acceptable sets of arguments. Value-based argumentation, as introduced by Bench-Capon (2003) [8], extends Dung?s framework. It takes into account the relative strength of arguments with respect to some ranking representing an audience: an argument is subjectively accepted if it is accepted with respect to some audience, it is objectively accepted if it is accepted with respect to all audiences.Deciding whether an argument is subjectively or objectively accepted, respectively, are computationally intractable problems. In fact, the problems remain intractable under structural restrictions that render the main computational problems for non-value-based argumentation systems tractable. In this paper we identify nontrivial classes of value-based argumentation systems for which the acceptance problems are polynomial-time tractable. The classes are defined by means of structural restrictions in terms of the underlying graphical structure of the value-based system. Furthermore we show that the acceptance problems are intractable for two classes of value-based systems that where conjectured to be tractable by Dunne (2007) [12].     

Algorithms for the computation of T-transitive closures

We present two weight-driven algorithms for the computation of the T-transitive closure of a symmetric binary fuzzy relation on a finite universe X with cardinality n (or, equivalently, of a symmetric (n/spl times/n)-matrix with elements in [0, 1]), with T a triangular norm. The first algorithm is proven to be valid for any triangular norm T, whereas the second algorithm is shown to be valid when T is either the minimum operator or an Archimedean triangular norm. Furthermore, we investigate how these algorithms can be appropriately adapted to generate the T-transitive closure of nonsymmetric binary fuzzy relations (or matrices) as well.