Systems and Implementations for Solving Reasoning Problems in Conditional Logics


Christoph Beierle

Presenter
Christoph Beierle, Department of Computer Science, University of Hagen, Germany

Bio
Christoph Beierle is a professor of computer science and head of the knowledge-based systems group in the Faculty of Mathematics and Computer Science at the University of Hagen, Germany. In 1985, he received his PhD in computer science from the University of Kaiserslautern, he was senior researcher at the Scientific Center of IBM Germany, and he is recipient of an IBM Outstanding Innovation Award. He has been working on algebraic specifications and formal approaches for software development and on methods for knowledge-based systems and their applications. His current research interests include modelling and reasoning with uncertain knowledge.

Abstract
Default rules like "If A, then usually B" or probabilistic rules like "If A, then B with probability x" are powerful constructs for knowledge representation. Such rules can be formalized as conditionals, denoted by (B|A) or (B|A)[x], and a conditional knowledge base consists of a set of conditionals. Different semantical models have been proposed for conditional knowledge bases, and the most important reasoning problems for conditional knowledge bases are to determine whether a knowledge base is consistent and to determine what a knowledge base entails. We present an overview on systems and implementations our group has been working on for solving reasoning problems in various semantics that have been developed for conditional knowledge bases. These semantics include quantitative, semi-quantitative, and qualitative conditional logics, based on both propositional logic and on first-order logic.

Selected Results and Related Issues of Confidentiality-Preserving Controlled Interaction Execution

Joachim Biskup

Presenter
Joachim Biskup, TU Dortmund, Germany

Bio
Joachim Biskup received his Diploma degree in mathematics from Technical University of Hannover and his Ph.D. in computer science from RWTH Aachen, Germany. He has been Professor of Computer Science at the University of Dortmund, University of Hildesheim and University of Dortmund again. He has performed research in recursion and complexity theory, information systems with an emphasis on schema design, query optimization and mediation, and various aspects of security, in particular access control and inference control.

Abstract
Controlled Interaction Execution has been developed as a security server for a specific kind of inference control shielding an isolated, logic-oriented information system when interacting over the time with a client by means of messages, in particular for query and transaction processing. The control aims at provably preserving confidentiality in a fully formalized sense, intuitively and simplifying rephrased as follows: Even when having (assumed) a priori knowledge, recording the interaction history, being aware of the details of the control mechanism, and unrestrictedly rationally reasoning, the client should never be able to infer the validity of any sentence declared as a potential secret in the security server's confidentiality policy. To enforce this goal, for each of a rich variety of specific situations a dedicated censor has been designed. As far as needed, a censor distorts a functionally expected reaction message such that suitably weakened or even believably incorrect information is communicated to the client.
We reconsider selected results of recent and ongoing work and discuss several issues for further research and development. The topics covered range from the impact of the underlying logic, whether propositional or first-order or non-monotonic about belief or an abstraction from any specific one, over the kind of the interactions, whether only queries or also view publishing or updates or revisions or even procedural programs, to the dynamic representation of control states, whether by simply logging or adapting the policy.

The Challenge of Optional Matching in SPARQL

Reinhard Pichler

Presenter
Reinhard Pichler, Faculty of Informatics, Vienna University of Technology, Austria

Bio
Reinhard Pichler holds a master's degree in Mathematics from the University of Innsbruck and a master's degree in Mathematical Computation from the University of London, QMW College. In 2000, he received his PhD in Computer Science from the Vienna University of Technology. From 1992 to 2005, he worked as software developer at the Program and Systems Engineering Department (PSE) of the Siemens AG Austria. Since 2005, he has been a Professor at the Faculty of Informatics of the Vienna University of Technology where he is leading the Database and Artificial Intelligence group. His main research interests in recent years have been in database theory - mainly on information integration and on foundational aspects of the semantic web query language SPARQL.

Abstract
Conjunctive queries (or, equivalently, SELECT-FROM-WHERE queries in SQL) are arguably the most widely used querying mechanism in practice and the most intensively studied one in database theory. Answering a conjunctive query (CQ) comes down to matching all atoms of the CQ simultaneously into the database. As a consequence, a CQ fails to provide any answer if the pattern described by the query does not exactly match the data. CQs might thus be too restrictive as a querying mechanism for data on the web, which is considered as inherently incomplete. The semantic web query language SPARQL therefore contains the OPTIONAL operator as a crucial feature. It allows the user to formulate queries which try to match parts of the query over the data if available, but do not destroy answers of the remaining query otherwise.
In this talk we will have a closer look at this optional matching feature of SPARQL. More specifically, we will concentrate on an interesting fragment of SPARQL - the so-called well-designed SPARQL graph patterns. They extend CQs by optional matching while imposing certain restrictions on how variables are allowed to occur in the query. We recall recent results that even in this small fragment of SPARQL most of the fundamental computational tasks become significantly harder than for conjunctive queries. For instance, query evaluation is now on the second level of the Polynomial Hierarchy and basic static analysis tasks such as containment or equivalence testing become even undecidable for well-designed SPARQL graph patterns. Also the semantics of query answering in the presence of ontologies (referred to as entailment regimes in SPARQL) has to be reconsidered in order to give intuitive results. It turns out that the seemingly small extension of CQs by optional matching has opened several interesting research opportunities.

Some Recent Trends in Argumentation Research

Henry Prakken

Presenter
Henry Prakken, Department of Information and Computing Sciences, Utrecht University & Faculty of Law, University of Groningen

Bio
Henry Prakken is a lecturer in Artificial Intelligence at the Department of Information and Computing Sciences, Utrecht University, and a professor in Legal Informatics and Legal Argumentation at the Law Faculty of the University of Groningen. He holds master degrees in law (1985) and philosophy (1988) from the University of Groningen. In 1993 he obtained his PhD degree (cum laude) at the Free University Amsterdam with a thesis titled Logical Tools for Modelling Legal Argument. His main research interests concern computational models of argumentation and their application in multi-agent systems, legal reasoning and other areas. Prakken is a past president of the International Association of AI & Law and the current president of the JURIX Foundation for Legal Knowledge-Based Systems and of the steering committee of the COMMA conferences on Computational Models of Argument. He is on the editorial board of several journals, including Artificial Intelligence.

Abstract
Argumentation is nowadays an important topic in symbolic AI research, especially in the study of nonmonotonic reasoning and the study of inter-agent communication. Argumentation makes explicit the reasons for the conclusions that are drawn and how conflicts between these reasons are resolved. This provides a natural mechanism to handle inconsistent and uncertain information and to resolve conflicts of opinion between intelligent agents. In this talk an overview will be given of some of the main current research issues, including the relation between abstract and structured models of argumentation and the relation between argumentation and probability theory.

Relational Complexity and Higher Order Logics

José María Turull Torres

Presenter
José María Turull Torres, Dept. of Engineering Universidad Nacional de La Matanza, Argentina, and Massey University, New Zealand

Bio
20 years of professional work in Informatics in Argentina and Mexico. A further 23 years of academic work with research in the areas of Database Theory, Finite Model Theory and Complexity, in Argentina and New Zealand. Currently appointed as a Professor in the Dept. of Engineering at Universidad Nacional de La Matanza, Argentina, and holding an Honorary Research Fellowship at Massey, N.Z. Member of the Program Committee in many international Conferences, and co-Chair in FoIKS 2004. Key-note Speaker in FMT in six int. Conferences. Many Refereed publications in journals like AMAI, APAL, J. of IGPL, JUCS, Acta Cybernetica, and TCS; chapters in books published by Springer, College Publications (London), Marcel Dekker, and AMS; editor in Springer and AMAI; articles in int. Conferences like FoIKS, CSL, IEEE Chilean SCCC, ETheCoM, EJC, ADC, and ADBIS. 2 Doctorate students and 4 Master students completed. Research visits and collaboration to U. of Helsinki, U. of Joensuu, U. of Tampere, U. of Warsaw, U. of Toronto, U. of Cantabria, Ecole Polytechnique de Paris, and Software Competence Centre Hagenberg.

Abstract
Relational machines (RM) were introduced in 1991 as abstract machines that compute queries to (finite) relational structures, or relational database instances (dbi's), that are generic (i.e., that preserve isomorphisms), and hence are more appropriate than Turing machines (TM) for query computation. RM's are TM's endowed with a relational store that holds the input dbi, as well as work relations, and can be queried and updated through first order logic (FO) formulas in their finite control. Consequently, k-ary RM's are incapable of computing the size of the input though, however, they can compute its sizek, i.e, the number of FOk types of k-tuples in the dbi. Then, it was a natural consequence to define a new notion of complexity suitable for RM's. Relational Complexity was also introduced in 1991 as a complexity theory where the input dbi to a query is measured as its sizek, and complexity classes mirroring computational complexity classes were defined. Relational Complexity turned out to be a theoretical framework in which we can characterize exactly the expressive power of the well-known fixed point quantifiers of a wide range of sorts. In 1997, several equivalences between fixed point quantifiers (added to FO) and different relational complexity classes were proved, classifying them as either deterministic, non-deterministic, or alternating, and either inflationary or non-inflationary. Those characterizations are actually very interesting and meaningful, given that it was already known that if we restrict the input to only ordered dbi's, the same equivalences with computational complexity classes also hold.
Regarding the characterization of relational complexity classes with other logics, it was proved that RM's have the same computation, or expressive power, as the (effective fragment of the) well known infinitary logic with finitely many variables. Besides, some fragments of second and third order logic, defined as semantic restrictions of the corresponding logic, have been proved to characterize several classes, and there is an ongoing work in that direction. One interesting consequence of it is that RM's are strong enough as to simulate the existence of third order relations in their relational store. An important application of the creation of new logics to Complexity Theory is the search for lower bounds of problems w.r.t. those logics, aiming to separate computational complexity classes.
In this talk we will give a description of RM's and NRM's, will define the basic notions of Relational Complexity, and discuss its motivations and the tight relationship between the main classes and different fixed point logics and fragments of second and third order logics.