Catálogo de publicaciones - libros

Often graphs are used to investigate properties of logic programs. In general, different graphs represent different kinds of information of the underlying programs. Sometimes this information is not sufficient for solving a certain problem. In this paper we define graphs which are for computing answer sets of logic programs. Intuitively, a graph associated to a logic program is suitable for answer set semantics if its structure is sufficient to compute the answer sets of the corresponding program. We identify different classes of graphs to be suitable for different classes of programs. We also give first experimental results showing the impact of the used graph type to one particular graph based algorithm for answer set computation.

The extended answer set semantics for simple logic programs, i.e. programs with only classical negation, allows for the defeat of rules to resolve contradictions. In addition, a partial order relation on the program’s rules can be used to deduce a preference relation on its extended answer sets. In this paper, we propose a “quantitative” preference relation that associates a weight with each rule in a program. Intuitively, these weights define the “cost” of defeating a rule. An extended answer set is preferred if it minimizes the sum of the weights of its defeated rules. We characterize the expressiveness of the resulting semantics and show that it can capture negation as failure. Moreover the semantics can be conveniently extended to sequences of weight preferences, without increasing the expressiveness. We illustrate an application of the approach by showing how it can elegantly express subgraph isomorphic approximation problems, a concept often used in intelligence analysis to find specific regions of interest in a large graph of observed activities.

In this note we discuss the expressive power of -calculi. We concentrate on those that are extensions of propositional modal logics with a fixpoint operator. The objective is to try to match the expressive power of monadic second-order logic. We consider different kinds of models: from trees and transition systems up to traces and timed systems.

Formal verification methods model systems by Kripke structures. In order to model live behaviors of systems, Kripke structures are augmented with . Such conditions partition the computations of the systems into fair computations, with respect to which verification proceeds, and unfair computations, which are ignored. Reasoning about Kripke structures augmented with fairness is typically harder than reasoning about non-fair Kripke structures. We consider the condition, where a computation is fair iff each transition that is enabled in infinitely often is also taken in infinitely often. Transition fairness is a natural and useful fairness condition. We show that reasoning about Kripke structures augmented with transition fairness is not harder than reasoning about non-fair Kripke structures. We demonstrate it for fair CTL and LTL model checking, and the problem of calculating the dominators and postdominators.

We propose a new parameter for the complexity of finite directed graphs which measures to what extent the cycles of the graph are intertwined. This measure, called entanglement, is defined by way of a game that is somewhat similar in spirit to the robber and cops games used to describe tree width, directed tree width, and hypertree width. Nevertheless, on many classes of graphs, there are significant differences between entanglement and the various incarnations of tree width.

Entanglement is intimately connected to the computational and descriptive complexity of the modal -calculus. On the one hand, the number of fixed point variables needed to describe a finite graph up to bisimulation is captured by its entanglement. This plays a crucial role in the proof that the variable hierarchy of the -calculus is strict.

In addition to this, we prove that parity games of bounded entanglement can be solved in polynomial time. Specifically, we establish that the complexity of solving a parity game can be parametrised in terms of the minimal entanglement of a subgame induced by a winning strategy.

The universal Horn theory of relational Kleene algebra with tests is of practical interest, particularly for program semantics, where Horn formulas can be used to verify correctness of programs or compiler optimizations. Unfortunately, this theory is known to be Π-complete. However, many formulas arising in practice fall into fragments of the theory that are of lower complexity. In this paper, we see that the location of occurrences of the Kleene asterate operator * within a formula has a great impact on complexity. Using syntactic criteria based on the location of *, we give a fragment of the theory that is Σ-complete, and a slightly larger fragment that is Π-complete. We show that the same results hold over *-continuous Kleene algebras with tests. The techniques exhibit a relationship between first-order logic and the Horn theories of relational and *-continuous Kleene algebra, even though the theories are not first-order axiomatizable.

In 1969, Tarski asked whether the arithmetic identities taught in high school are complete for showing all arithmetic equations valid for the natural numbers. We know the answer to this question for various subsystems obtained by restricting in different ways the language of arithmetic expressions, yet, up to now we knew nothing of the original system that Tarski considered when he started all this research, namely the theory of integers under sum, product, exponentiation with two constants for zero and one.

This paper closes this long standing open problem, by providing an elementary proof, relying on previous work of R. Gurevič, of the fact that Tarski’s original system is decidable, yet not finitely aximatisable.

We also show some consequences of this result for the theory of isomorphisms of types.

Circumscription is one of the most important and well studied formalisms in the realm of nonmonotonic reasoning. The inference problem for propositional circumscription has been extensively studied from the viewpoint of computational complexity. We prove that there exists a trichotomy for the complexity of the inference problem in propositional variable circumscription. More specifically we prove that every restricted case of the problem is either -complete, coNP-complete, or in P.

Complete algorithms for constraint solving typically exploit properties like (in)consistency or interchangeability, which they detect by means of incomplete yet effective algorithms and use to reduce the search space. In this paper, we study a wide range of properties which includes most of the ones used by existing CSP algorithms as well as some which have not yet been considered in the literature, and we investigate their use in CSP solving. We clarify the relationships between these notions and characterise the complexity of the problem of checking them. Following the CSP approach, we then determine a number of relaxations (for instance versions) which provide sufficient conditions whose detection is tractable. This work is a first step towards a comprehensive framework for CSP properties, and it also shows that new notions still remain to be exploited.

We describe a novel decision procedure for Quantified Boolean Formulas (QBFs) which aims to unleash the hidden potential of quantified reasoning in applications. The Skolem theorem acts like a glue holding several ingredients together: BDD-based representations for boolean functions, search-based QBF decision procedure, and compilation-to-SAT techniques, among the others. To leverage all these techniques at once we show how to evaluate QBFs by symbolically reasoning on a compact representation for the propositional expansion of the skolemized problem. We also report about a first implementation of the procedure, which yields very interesting experimental results.