Search ACM DL

Search Issue

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

DOI: 10.1145/2499937.2499938

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

**Does Treewidth Help in Modal Satisfiability?**

M. Praveen

Article No.: 18

DOI: 10.1145/2499937.2499939

Many tractable algorithms for solving the Constraint Satisfaction Problem (*incidence...
*

*
Graph Reachability and Pebble Automata over Infinite Alphabets
Tony Tan
Article No.: 19
DOI: 10.1145/2499937.2499940
*

*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
DOI: 10.1145/2499937.2499941
*

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

*
Extensional Higher-Order Logic Programming
Angelos Charalambidis, Konstantinos Handjopoulos, Panagiotis Rondogiannis, William W. Wadge
Article No.: 21
DOI: 10.1145/2499937.2499942
*

*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
DOI: 10.1145/2499937.2499943
*

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

*
Common Knowledge in Email Exchanges
Floor Sietsma, Krzysztof R. Apt
Article No.: 23
DOI: 10.1145/2499937.2499944
*

*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
DOI: 10.1145/2499937.2499945
*

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