Nonmonotonic Logic
Algebras of Measurements: the logical structure of Quantum Mechanics
Lehmann, Daniel, Engesser, Kurt, Gabbay, Dov M.
In Quantum Physics, a measurement is represented by a projection on some closed subspace of a Hilbert space. We study algebras of operators that abstract from the algebra of projections on closed subspaces of a Hilbert space. The properties of such operators are justified on epistemological grounds. Commutation of measurements is a central topic of interest. Classical logical systems may be viewed as measurement algebras in which all measurements commute. Keywords: Quantum measurements, Measurement algebras, Quantum Logic. PACS: 02.10.-v.
A Redefinition of Arguments in Defeasible Logic Programming
Viglizzo, Ignacio Darío (Universidad Nacional del Sur, Bahía Blanca, Argentina) | Tohmé, Fernando (Universidad Nacional del Sur, Bahía Blanca) | Simari, Guillermo (Universidad Nacional del Sur, Bahía Blanca)
Defeasible Logic Programming (DELP) is a formalism that extends declarative programming to capture defeasible reasoning. Its inference mechanism, upon a query on a literal in a program, answers by indicating whether or not it is warranted in an argumentation process. While the properties of DELP are well known, some of its basic elements can be redefined in order to shed light on some of the subtleties of the warrant process. We will discuss these alternative definitions and the cases in which they provide a better performance.
Using Defeasible Logic Programming with Contextual Queries for Developing Recommender Servers
Tucat, Mariano (UNS - CONICET) | Garcia, Alejandro Javier (UNS - CONICET) | Simari, Guillermo Ricardo (UNS)
In this work we introduce a defeasible logic programming recommender server that accepts different types of queries from client agents that can be distributed in remote hosts. We formalize new ways of querying recommender servers containing specific information or preferences, and creating a particular context for the queries. This special type of queries (called contextual queries) allows recommender servers to compute recommendations for any client using its preferences, and will be answered using an argumentative inference mechanism. We focus on a particular implementation of recommended systems that extends the integration of argumentation and recommender systems to a multi-agent setting. Our approach is based on a DeLP-server that can answer queries from agents in remote hosts. Since client agents can consult different domain specific recommender servers, then, multiple configurations of clients and servers can be defined.
The Complexity of Circumscription in DLs
Bonatti, P. A., Lutz, C., Wolter, F.
As fragments of first-order logic, Description logics (DLs) do not provide nonmonotonic features such as defeasible inheritance and default rules. Since many applications would benefit from the availability of such features, several families of nonmonotonic DLs have been developed that are mostly based on default logic and autoepistemic logic. In this paper, we consider circumscription as an interesting alternative approach to nonmonotonic DLs that, in particular, supports defeasible inheritance in a natural way. We study DLs extended with circumscription under different language restrictions and under different constraints on the sets of minimized, fixed, and varying predicates, and pinpoint the exact computational complexity of reasoning for DLs ranging from ALC to ALCIO and ALCQO. When the minimized and fixed predicates include only concept names but no role names, then reasoning is complete for NExpTime^NP. It becomes complete for NP^NExpTime when the number of minimized and fixed predicates is bounded by a constant. If roles can be minimized or fixed, then complexity ranges from NExpTime^NP to undecidability.
On the Accrual of Arguments in Defeasible Logic Programming
Lucero, Mauro Javier Gómez (Universidad Nacional del Sur (UNS)) | Chesñevar, Carlos Iván (Universidad Nacional del Sur (UNS)) | Simari, Guillermo Ricardo (Universidad Nacional del Sur (UNS))
Recently, the notion of accrual of arguments has received some attention from the argumentation community. Three principles for argument accrual have been identified as necessary to hold in argumentation frameworks. In this paper we propose an approach to model the accrual of arguments in the context of Defeasible Logic Programming, a logic programming approach to argumentation which has proven to be successful for many real-world applications. We will analyze the above mentioned principles in the context of our proposal, studying other interesting properties.
Preferences and Nonmonotonic Reasoning
Brewka, Gerhard (University of Kentucky) | Niemela, Ilkka | Truszczynski, Miroslaw
Selecting extended logic programming with the answer-set semantics as a "generic" nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. Finally, we comment on formalisms which explicitly represent preferences on properties of belief sets. Such formalisms either build preference information directly into rules and modify the semantics of the logic appropriately, or specify preferences on belief sets independently of the mechanism to define them.
Preferences and Nonmonotonic Reasoning
Brewka, Gerhard (University of Kentucky) | Niemela, Ilkka | Truszczynski, Miroslaw
We give an overview of the multifaceted relationship between nonmonotonic logics and preferences. We discuss how the nonmonotonicity of reasoning itself is closely tied to preferences reasoners have on models of the world or, as we often say here, possible belief sets. Selecting extended logic programming with the answer-set semantics as a "generic" nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. We discuss how such conflicts can be resolved based on implicit specificity or on explicit rankings of defaults. Finally, we comment on formalisms which explicitly represent preferences on properties of belief sets. Such formalisms either build preference information directly into rules and modify the semantics of the logic appropriately, or specify preferences on belief sets independently of the mechanism to define them.
From Qualitative to Quantitative Proofs of Security Properties Using First-Order Conditional Logic
A first-order conditional logic is considered, with semantics given by a variant of ǫ-semantics (Adams 1975; Goldszmidt & Pearl 1992), where ϕ ψ means that Pr(ψ ϕ) approaches 1 super-polynomially--faster than any inverse polynomial. This type of convergence is needed for reasoning about security protocols. A complete axiomatization is provided for this semantics, and it is shown how a qualitative proof of the correctness of a security protocol can be automatically converted to a quantitative proof appropriate for reasoning about concrete security.
Remarks on Inheritance Systems
We try a conceptual analysis of inheritance diagrams, first in abstract terms, and then compare to "normality" and the "small/big sets" of preferential and related reasoning. The main ideas are about nodes as truth values and information sources, truth comparison by paths, accessibility or relevance of information by paths, relative normality, and prototypical reasoning.
CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements
Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., Poole, D.
Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.