enter search term and/or author name
Constraint Propagation for First-Order Logic and Inductive Definitions
Johan Wittocx, Marc Denecker, Maurice Bruynooghe
Article No.: 17
In Constraint Programming, constraint propagation is a basic component of constraint satisfaction solvers. Here we study constraint propagation as a basic form of inference in the context of first-order logic (FO) and extensions with inductive...
Many tractable algorithms for solving the Constraint Satisfaction Problem (
Graph Reachability and Pebble Automata over Infinite Alphabets
Article No.: 19
Let D denote an infinite alphabet -- a set that consists of infinitely many symbols. A word...
Parameterized Complexity of DPLL Search Procedures
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria
Article No.: 20
We study the performance of DPLL algorithms on parameterized problems. In particular, we investigate how difficult it is to decide whether small solutions exist for satisfiability and other combinatorial problems. For this purpose we develop a...
We propose a purely extensional semantics for higher-order logic programming. In this semantics program predicates denote sets of ordered tuples, and two predicates are equal iff they are equal as sets. Moreover, every program has a unique minimum...
On the Inference of Resource Usage Upper and Lower Bounds
Elvira Albert, Samir Genaim, Abu Naser Masud
Article No.: 22
Cost analysis aims at determining the amount of resources required to run a program in terms of its input data sizes. The most challenging step is to infer the cost of executing the loops in the program. This requires bounding the...
We consider a framework in which a group of agents communicates by means of emails, with the possibility of replies, forwards and blind carbon copies (BCC). We study the epistemic consequences of such email exchanges by introducing an appropriate...
Propositional Update Operators Based on Formula/Literal Dependence
Andreas Herzig, Jerome Lang, Pierre Marquis
Article No.: 24
We present and study a general family of belief update operators in a propositional setting. Its operators are based on formula/literal dependence, which is more fine-grained than the notion of formula/variable dependence that was...