ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 10 Issue 1, January 2009

Specifying norm-governed computational societies
Alexander Artikis, Marek Sergot, Jeremy Pitt
Article No.: 1
DOI: 10.1145/1459010.1459011

Electronic markets, dispute resolution and negotiation protocols are three types of application domains that can be viewed as open agent societies. Key characteristics of such societies are agent heterogeneity, conflicting individual goals and...

Arithmetic complexity
Lou Van Den Dries, Yiannis N. Moschovakis
Article No.: 2
DOI: 10.1145/1459010.1459012

We obtain lower bounds on the cost of computing various arithmetic functions and deciding various arithmetic relations from specified primitives. This includes lower bounds for computing the greatest common divisor and deciding coprimeness...

Certainty closure: Reliable constraint reasoning with incomplete or erroneous data
Neil Yorke-Smith, Carmen Gervet
Article No.: 3
DOI: 10.1145/1459010.1459013

Constraint Programming (CP) has proved an effective paradigm to model and solve difficult combinatorial satisfaction and optimization problems from disparate domains. Many such problems arising from the commercial world are permeated by data...

New results on rewrite-based satisfiability procedures
Alessandro Armando, Maria Paola Bonacina, Silvio Ranise, Stephan Schulz
Article No.: 4
DOI: 10.1145/1459010.1459014

Program analysis and verification require decision procedures to reason on theories of data structures. Many problems can be reduced to the satisfiability of sets of ground literals in theory T. If a sound and complete...

Reasoning about actions with sensing under qualitative and probabilistic uncertainty
Luca Iocchi, Thomas Lukasiewicz, Daniele Nardi, Riccardo Rosati
Article No.: 5
DOI: 10.1145/1459010.1459015

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We first define the action language E for reasoning about actions with sensing, which has a semantics based on the autoepistemic...

A finite equational base for CCS with left merge and communication merge
Luca Aceto, Wan Fokkink, Anna Ingolfsdottir, Bas Luttik
Article No.: 6
DOI: 10.1145/1459010.1459016

Using the left merge and the communication merge from ACP, we present an equational base (i.e., a ground-complete and ω-complete set of valid equations) for the fragment of CCS without recursion, restriction and relabeling modulo (strong)...

A logical characterization of the counting hierarchy
Juha Kontinen
Article No.: 7
DOI: 10.1145/1459010.1459017

In this article we give a logical characterization of the counting hierarchy. The counting hierarchy is the analogue of the polynomial hierarchy, the building block being Probabilistic polynomial time PP instead of NP. We show that the extension...