Conference Program

The Twelfth International Conference on the Principles of Knowledge Representation and Reasoning would like to announce an impressive list of invited speakers and tutorials.

• Ron Brachman and Hector Levesque: Great moments in KR: The 1984 Complexity Convergence (a joint session with AAMAS). This talk is sponsored by IBM.
  Abstract: The 1970's were a fertile and exciting time for Artificial Intelligence. This was especially true in the area of Knowledge Representation, where numerous novel languages and systems were created and debated, and a burgeoning set of AI applications were supported by frames, semantic networks, production rules, and other idiosyncratic KR schemes.  But the issues under debate were often vague, and intuition and implementation-based arguments reigned, with little or no formal basis for discussion.  Fortunately, in the late '70's and early '80's, out of this energetic but murky environment emerged several important lines of thought that promised to put elements of the field on a firmer foundation.  By 1984 these threads had been developed enough that they could be knitted together, and out of this convergence a new kind of formal analysis of KR systems became possible.  We look at the birth and evolution of several key ideas and how they came together to allow us to draw some interesting conclusions about the computational complexity of core inferences in a mainstream form of KR.  We also make some observations about the aftermath, and how that moment in the history of the field seemed to mark a sea change in approaches to Knowledge Representation.

• Ian Horrocks: Scalable Ontology Systems. This talk is sponsored by European Coordinating Committee for Artificial Intelligence (ECCAI)
  Abstract: Ontologies and ontology based systems are rapidly becoming mainstream technologies, with RDF and OWL now being deployed in diverse application domains, and with major technology vendors starting to augment their existing systems with ontological reasoning. For example, Oracle Inc. recently enhanced its well-known database management system with modules that use RDF/OWL ontologies to support "semantic data management", and their product brochure lists numerous application areas that can benefit from this technology, including Enterprise Information Integration, Knowledge Mining, Finance, Compliance Management and Life Science Research.  While gratifying to the KR research community, this success also brings with it many challenges. In particular, ontology reasoning systems will need to exhibit robust scalability if deployments in large scale applications are to be successful. In this talk I will review the evolution of ontology systems to date, and show how KR theory developed into a mainstream technology. I will then go on to examine the challenges arising from deployment in large scale applications, and discuss recent research aimed at addressing them.

• Yoav Shoham: Logics of Intention and the Database Perspective
  Abstract: The seminal paper by Cohen and Levesque, trying to capture in logic certain intuitions about intention and its relation with other mental constructs, has been followed up by a series of papers proposing various amendments to the original proposal. I will suggest a slight twist on the subject, one that is based on an unabashed computational perspective. I will discuss this so-called "database perspective", as well as some of its subtle logical implications.

• Chitta Baral: Reasoning about Actions and Change: From Single Agent Actions to Multi-agent Actions.
  Abstract: We often deal with dynamic worlds where actions are executed by agents and events may happen. Example of such worlds range from virtual worlds such as the world of a database to robots and humans in physical worlds. To understand the dynamics of such worlds as well as to be able to assert some control over such worlds one needs to reason about the actions and events and how they may change the world. In this invited talk we will present some of the important results in this field and present some future directions. In particular, we will discuss how theories and results from reasoning about actions and change can be combined with theories and results in dynamic epistemic logics to obtain a unified theory of multi-agent actions.

• Leonardo de Moura: Satisfiability with and without Theories.
• Carsten Lutz: Reasoning in DLs: Expressive Power vs. Computational Complexity
• Bernhard Nebel: Computational Complexity of Action Planning.
• mc schraefel: What if you Wanted someone (else) to Use this? Usability Heuristics for KR tool & representation design.

Abstracts of tutorials on Sunday, May 9, 2010

• Carsten Lutz
  Reasoning in DLs: Expressive Power vs. Computational Complexity
  Abstract:
  Description logics (DLs) are a popular family of knowledge representation formalisms that play an important role as a logical foundation of ontology languages such as OWL and aim at providing a good compromise between representational capabilities (i.e., expressive power) and the computational complexity of reasoning.  The fact that different applications require different such compromises has led to the development of a large toolbox of DLs that range from inexpressive but computationally efficient to very expressive but computationally challenging, thus catering for various needs and requirements.

  This tutorial provides a comprehensive tour of reasoning in modern description logics with an emphasis on computational complexity. It covers expressive DLs such as the SHIQ family, explaining which kind of expressive power tends to make reasoning more complex, and why. It also covers inexpressive DLs such as the EL and DL-Lite families, explaining their good computational behaviour and highlighting the limits of polytime reasoning. On top of the traditional reasoning problems such as subsumption and satisfiability, the tutorial also addresses query answering over instance data in the presence of DL ontologies, a more recent reasoning problem that rapidly gains importance in applications. In particular, we will explain how the complexity landscape differs for traditional reasoning and for query answering, and take a brief look at computational complexity issues raised by implementations of DL query anwering based on standard relational database systems.  Throughout the tutorial, connections to the W3C-standard OWL are drawn whenever possible.



• Leonardo de Moura
  Satisfiability with and without Theories.
  Abstract:
  Constraint satisfaction problems arise in many diverse areas including software and hardware verification, type inference, extended static checking, test-case generation, scheduling, planning, graph problems, among others. The most well-known constraint satisfaction problem is propositional satisfiability SAT. Of particular recent interest is Satisfiability Modulo Theories (SMT), where the interpretation of some symbols is constrained by a background theory. For example, the theory of arithmetic restricts the interpretation of symbols such as: +, ≤, 0, and 1.
  SMT draws on the most prolific problems in the past century of symbolic logic: the decision problem, completeness and incompleteness of logical theories, and finally complexity theory. In this tutorial, we will describe a brief introduction to the theory behind SAT & SMT solvers, the main techniques, and their many applications. In particular, we will describe how these solvers are used at Microsoft.


• Bernhard Nebel
  Computational Complexity of Action Planning.
  Abstract:
  After a brief introduction of different planning frameworks and a short introduction to computational complexity theory, we will examine computational complexity results for different planning frameworks and planning domains. In order to get an idea of how changes in expressiveness can affect the applicability of planning methods, we will also have a look at compilation techniques that allow us to assess the expressive power of a planning formalism.


• mc schraefel:
  What if you Wanted someone (else) to Use this? Usability Heuristics for KR tool & representation design.
  Abstract:
  The User Interface or User Experience of a tool in KR may be one of the last things on a researcher's mind when trying to find a path towards exploring a problem or automating components to build a solution. And that's fine if the author of the tool is the only person who will ever use the tool, but what if there's a desire to share the tool with someone else? There are some straight ahead heuristics about designing both the interaction with tool components and with the representations that a tool produces to help with usability for domain experts and potentially even legibility of what the tool produces for interested persons outside the domain. There are likewise some lightweight mechanisms to evaluate whether the proposed design will achieve either of these ends before the code is implemented.

  The purpose of this tutorial will be to walk through design heuristics for interaction and representation. At the end of the tutorial participants will be able to assess tool effectiveness against these criteria, propose approaches for revision, and work through approaches for lightweight usability assessment of their proposal.

Please visit regularly for more news.