1,721,037 research outputs found
Research assessment: A contribution to solving the publication credit allocation problem
Full text linkIn allocation problems, a given set of goods are assigned to agents in such a way that the social welfare is
maximised, that is, the largest possible global worth is achieved. When goods are indivisible, it is possible to
use money compensation to perform a fair allocation taking into account the actual contribution of all agents
to the social welfare. Coalitional games provide a formal mathematical framework to model such problems,
in particular the Shapley value is a solution concept widely used for assigning worths to agents in a fair way.
Unfortunately, computing this value is a #P-hard problem, so that applying this good theoretical notion is often
quite difficult in real-world problems
Negation and minimality in non-Horn databases
No full textIn this work we generalize the semantics for negation in logic programs, putting together the constructive nature of the rule-based deductive database with the syntax-independence of the closed-world reasoning rules. These generalized semantics are shown to be a well-motivated and well-founded alternative to closed-world assumptions since they enjoy nice semantic and computational properties
On the Complexity of Finding Second-Best Abductive Explanations
No full textWhile looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is
ICARUS: Intelligent content-based retrieval of 3D scene
No full textWe present a tool for the analysis, classification and content-based retrieval of 3D scene. The system ICARUS analyzes files in VRML format, searching for the presence of complex 3D-objects and relative geometrical relationships between them. Descriptions of the virtual scenes are classified in a Terminological System, and reasoning mechanisms are used for querying
Arbitration (or how to merge knowledge bases)
No full textKnowledge-based systems must be able to "intelligently" manage a large amount of information coming from different sources and at different moments in time. Intelligent systems must be able to cope with a changing world by adopting a "principled" strategy. Many formalisms have been put forward in the artificial intelligence (Al) and database (DB) literature to address this problem. Among them, belief revision is one of the most successful frameworks to deal with dynamically changing worlds. Formal properties of belief revision have been investigated by Alchourron, Gardenfors, and Makinson, who put forward a set of postulates stating the properties that a belief revision operator should satisfy. Among these properties, a basic assumption of revision is that the new piece of information is totally reliable and, therefore, must be in the revised knowledge base. Different principles must be applied when there are two different sources of information and each one has a different view of the situation-the two views contradicting each other. If we do not have any reason to consider any of the sources completely unreliable, the best we can do is to "merge" the two views in a new and consistent one, trying to preserve as much information as possible. We call this merging process arbitration. In this paper, we investigate the properties that any arbitration operator should satisfy. In the style of Alchourron, Gardenfors, and Makinson we propose a set of postulates, analyze their properties, and propose actual operators for arbitration
The complexity of model checking for propositional default logics
No full textWe analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature: Reiter's, Justified, constrained, rational, and cumulative. We prove that all the analyzed variants are Sigma(p)(2)-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Sigma(p)(2)-complete even if all defaults are normal and prerequisite-free. The other semantics are Delta(p)(2)[log n]-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively. (c) 2005 Elsevier B.V. All rights reserved
The complexity of model checking for propositional default logics
No full textDefault logic is one of the most widely used formalisms to formalize commonsense reasoning. In this paper we analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature. We prove that all the analyzed variants have the same complexity and that this problem is in general Sigma(2)(p) complete, while it is coNP complete under some restrictions on the form of the defaults
- …
