Search

Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of "neighbors" occurring with them in the coalition that emerged. Within this setting, the computational complexity of a number of relevant reasoning tasks is studied, by charting a clear picture of the intrinsic difficulty of finding "agreements" among the agents. Specific algorithmic approaches to reason about such social environments are proposed under the utilitarian perspective, where the collective utility of a coalition is the sum of the utilities of the individuals, as well as under the egalitarian perspective, with the goal being to maximize the utility of the least satisfied agent. These algorithms have been implemented and results of experimental activity are discussed, too. [ABSTRACT FROM AUTHOR]

Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of "neighbors" occurring with them in the coalition that emerged. Within this setting, the computational complexity of a number of relevant reasoning tasks is studied, by charting a clear picture of the intrinsic difficulty of finding "agreements" among the agents. Specific algorithmic approaches to reason about such social environments are proposed under the utilitarian perspective, where the collective utility of a coalition is the sum of the utilities of the individuals, as well as under the egalitarian perspective, with the goal being to maximize the utility of the least satisfied agent. These algorithms have been implemented and results of experimental activity are discussed, too. [ABSTRACT FROM AUTHOR]

Belief merging aims to combine pieces of information from different (and possibly conflicting) sources so as to produce a single consistent belief base which retains as much information as possible. In this paper, we describe Merginator, a logic-based tool implementing three belief merging operators presented with specific characteristics that make them interesting for comparison: ΔΣ, ΔGMax and Δps. We describe these operators while solving a set of basic examples found in the literature that we translate into natural language to provide insights for Merginator users. We also propose two more complex consensus-seeking examples: an adaptation to the role play “Lost at Sea” and the subject of administrative response to air pollution in Hong Kong. Results show that all three operators provide a consensus to the scenarios, and Δps gives the most refined consensus. This demonstrates that belief merging, is a viable technique to support consensus decision-making in many domains. Merginator is open source software available at GitHub. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the concept of random truth degree of an abstract proposition, which is a common generalization of various concepts of truth degree existing in literature, and prove that the set of random truth degree of all propositions has no isolated points in the real unit interval I = [0, 1]. We define random resemblance degree and random logic pseudo-metric among two propositions by means of random truth degrees, and prove that the random logic pseudo-metric space has no isolated points. By virtue of integral convergence theorem in probability theory we give a limit theorem of random truth degrees, which shows the connection of various truth degrees existing in literature. As an application we propose two diverse approximate reasoning models in random logic pseudo-metric space. [ABSTRACT FROM AUTHOR]

Knowledge representation and automated reasoning are two of the pillars of Artificial Intelligence but, differently from other pillars, they are strictly intertwined. Depending on how knowledge is represented, different types of reasoning can be applied and, on the other hand, new developments in the automated reasoning column fosters new ideas on the knowledge representation side. The Italian community has been always very involved in these fascinating themes, and this is witnessed by the lively group of knowledge representation and automated reasoning (Rappresentazione della Conoscenza e Ragionamento Automatico, RCRA) of AI*IA. In this paper we survey the developments on automated reasoning in the last 25 years, with particular emphasis on the research of the Italian community and of the RCRA group. The focus will be mainly on the algorithmic side, while a companion paper focuses more on the knowledge representation side, and on the vast area of semantic technologies. [ABSTRACT FROM AUTHOR]

We devise a resolution calculus that tests the satisfiability of infinite families of clause sets, called clause set schemata. For schemata of propositional clause sets, we prove that this calculus is sound, refutationally complete, and terminating. The calculus is extended to first-order clauses, for which termination is lost, since the satisfiability problem is not semi-decidable for nonpropositional schemata. The expressive power of the considered logic is strictly greater than the one considered in our previous work. [ABSTRACT FROM AUTHOR]

Policy-based inference control of queries submitted to a logic-oriented information system aims at confining answers to queries such that the user cannot infer the validity of any sentence specified in a confidentiality policy. Such a control requires us to consider the history of queries and answers to a particular user. In most previous approaches, the control system captures the history by maintaining a fictitious view the user is supposed to generate by exploiting rational reasoning. In this paper, we propose and explore an alternative option to represent the history, namely by suitably adapting the confidentiality policy after returning an answer to a query. Basically, such a policy adaptation precomputes all relevant steps of formal proofs that the fictitious view logically implies some policy element. Focusing on propositional information systems, we present a comprehensive protocol for policy adaptation, which always keeps the current version of the confidentiality policy redundancy-free and fully vulnerable. This protocol is formally proved to be effective by a reduction argument, showing that policy adaptation is able to simulate the achievements of maintaining a view. We also briefly discuss the efficiency for special cases under dedicated data structures. [ABSTRACT FROM AUTHOR]

Inference control aims at disabling a participant to gain a piece of information to be kept confidential. Considering a server-client architecture for information systems, we extend Controlled Query Evaluation (CQE), an inference control method to enforce confidentiality in static information systems under queries, to databases that are updatable by a client. More specifically, within the framework of the lying approach to CQE, we study how the server should translate a view update request issued by a client into a new database state in an inference-proof way. In order to avoid dangerous inferences, some such updates have to be denied even though the new database instance would be compatible with the set of integrity constraints declared in the schema and supposed to be known to the client. In contrast, seen from the client's point of view some other updates leading to an incompatible instance should not be denied. We design a control method to resolve this seemingly paradoxical situation and then prove that the general security definitions of CQE, suitably extended to capture both query evaluation and view update processing, and other properties linked to view updates hold. Moreover, we further enhance that control method by adding an inference-proof subprotocol for refreshing the views of the other clients. To ensure inference-proofness, from the other clients' point of view, any view update might be a transaction, i.e., a sequence of elementary updates. This article extends, elaborates and clarifies our contribution [12] to DBSec 2009 and also comprises some results of our work [9] presented at ESORICS 2009. [ABSTRACT FROM AUTHOR]

Database design aims to find a database schema that permits the efficient processing of common types of queries and updates on future database instances. Full first-order hierarchical decompositions constitute a large class of database constraints that can provide assistance to the database designer in identifying a suitable database schema. We establish finite axiomatisations of full first-order hierarchical decompositions that mimic best database design practice. That is, an inference engine derives all the independent collections of the universal schema during database normalization, and the designer determines during database denormalization which re-combinations of these independent collections manifest the final database schema. We also show that well-known correspondences between multivalued dependencies, degenerated multivalued dependencies, and a fragment of Boolean propositional logic do not extend beyond binary full first-order hierarchical decompositions. [ABSTRACT FROM AUTHOR]

This paper points out that the notion of non-conservative extension of a knowledge base (KB) is important to the distributed logical setting of peer-to-peer inference systems (P2PIS), a.k.a. peer-to-peer semantic systems. It is useful to a peer in order to detect/prevent that a P2PIS corrupts (part of) its knowledge or to learn more about its own application domain from the P2PIS. That notion is all the more important since it has connections with the privacy of a peer within a P2PIS and with the quality of service provided by a P2PIS. We therefore study the following tightly related problems from both the theoretical and decentralized algorithmic perspectives: (i) deciding whether a P2PIS is a conservative extension of a given peer and (ii) computing the witnesses to the corruption of a given peer's KB within a P2PIS so that we can forbid it. We consider here scalable P2PISs that have already proved useful to Artificial Intelligence and DataBases. [ABSTRACT FROM AUTHOR]

Controlled Query Evaluation (CQE) defines a logical framework to protect confidential information in a database. By modeling a user's a priori knowledge appropriately, a CQE system not only controls access to certain database entries but also accounts for information inferred by the user. In this article, we present a static (preprocessing) CQE-approach for propositional databases with an availability policy. The resulting inference-proof and availability-preserving database ensures confidentiality of secret information while guaranteeing availability of certain database entries to a highest degree possible. We illustrate the semantics of the system by a comprehensive example and state the essential requirements for an inference-proof and availability-preserving database. We present an algorithm that accomplishes the preprocessing by combining SAT solving and “Branch and Bound”. [ABSTRACT FROM AUTHOR]