ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 14 Issue 3, August 2013

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 (Csp) have been developed using the notion of the treewidth of some graph derived from the input Csp instance. In particular, the 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...