enter search term and/or author name
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...
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
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
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
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
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
Article No.: 7
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...