In this paper, we present an alternative to the Turing Test that has some conceptual and practical advantages. A Winograd schema is a pair of sentences that differ only in one or two words and that contain a referential ambiguity that is resolved in opposite directions in the two sentences. We have compiled a collection of Winograd schemas, designed so that the correct answer is obvious to the human reader, but cannot easily be found using selectional restrictions or statistical techniques over text corpora. A contestant in the Winograd Schema Challenge is presented with a collection of one sentence from each pair, and required to achieve human-level accuracy in choosing the correct disambiguation.

Answering queries in information systems that allow for ex- pressive inferencing is currently a field of intense research. This problem is often referred to as ontology-based data ac- cess (OBDA). We focus on conjunctive query entailment un- der logical rules known as tuple-generating dependencies, existential rules or Datalog+/-. One of the most expressive decidable classes of existential rules known today is that of greedy bounded treewidth sets (gbts). We propose an algo- rithm for this class, which is worst-case optimal for data and combined complexities, with or without bound on the pred- icate arity. A beneficial feature of this algorithm is that it allows for separation between offline and online processing steps: the knowledge base can be compiled independently from queries, which are evaluated against the compiled form. Moreover, very simple adaptations of the algorithm lead to worst-case-optimal complexities for specific subclasses of gbts which have lower complexities, such as guarded rules.

Fixpoints play a key role in the mathematical set up of abstract argumentation theory but, we argue, have been relatively underexamined in the literature. The paper studies the logical structure underlying the computation via approximation sequences of the sort of fixpoints relevant in argumentation. Concretely, it presents a number of novel results on the fixed point theory underpinning the main Dung's semantics and, inspired by recent literature on the logical analysis of equilibrium computation in games, it provides a characterization of those semantics in terms of iterated model updates.

Workshop on Knowledge-Intensive Business (KR&R) has long been a vibrant and exciting Processes (KiBP 2012). It has emerged from 256 registered abstracts. It was significantly more an understanding of how to store, retrieve, and interact than the 161 submissions to KR 2002, but somewhat with knowledge, and at the development of fewer than the record set at KR 2008 of 251 submissions. John McCarthy, recognized tasks such as planning, diagnosis, argumentation, by many as the founder of AI and KR, passed away and belief revision. KR 2012 will pay tribute to John gathering for researchers working on different aspects through an invited lecture by Leora Morgenstern of KR&R, and fosters communication, crossfertilization entitled "rough the Lens of Drosophila: John Mc-of ideas, and collaboration across research Carthy's Quest for Human-Level Artificial Intelligence."

Belief change studies how to update knowledge bases used for reasoning. Traditionally belief revision has been based on full propositional logic. However, reasoning with full propositional knowledge bases is computationally hard, whereas reasoning with Horn knowledge bases is fast. In the past several years, there has been considerable work in belief revision theory on developing a theory of belief contraction for knowledge represented in Horn form. Our main focus here is the computational complexity of belief contraction, and, in particular, of various methods and approaches suggested in the literature. This is a natural and important question, especially in connection with one of the primary motivations for considering Horn representation: efficiency. The problems considered lead to questions about Horn envelopes (or Horn LUBs), introduced earlier in the context of knowledge compilation. This work gives a syntactic characterization of the remainders of a Horn belief set with respect to a consequence to be contracted, as the Horn envelopes of the belief set and an elementary conjunction corresponding to a truth assignment satisfying a certain explicitly given formula. This gives an efficient algorithm to generate all remainders, each represented by a truth assignment. On the negative side, examples are given of Horn belief sets and consequences where Horn formulas representing the result of contraction, based either on remainders or on weak remainders, must have exponential size for almost all possible choice functions (i.e., different possible choices of partial meet contraction). Therefore using the Horn framework for belief contraction does not by itself give us computational efficiency. Further work is required to explore the possibilities for efficient belief change methods.

The advance of Internet and Sensor technology has brought about new challenges evoked by the emergence of continuous data streams. While existing data-stream management systems allow for high-throughput stream processing, they lack complex reasoning capacities. We address this shortcoming and elaborate upon an approach to knowledge-intense stream reasoning based on Answer Set Programming (ASP). The emphasis thus shifts from rapid data processing to complex reasoning. To accommodate this in ASP, we develop new techniques that allow us to formulate problem encodings dealing with emerging as well as expiring data in a seamless way. We thus propose novel language constructs and modeling techniques for specifying and reasoning with time-decaying logic programs.

When agents need to make decisions on multiple issues, applying common voting rules becomes computationally hard due to the exponentially large number of alternatives. One computationally efficient solution is to vote on the issues sequentially. In this paper, we investigate how well the winner under the sequential voting process approximates the winners under some common voting rules that admit natural scoring functions that can serve as a basis for approximation results. We focus on multi-issue domains where each issue is binary and the agents' preferences are O-legal, separable, represented by LP-trees, or lexicographic. We show some generalized paradoxes of multiple elections: Sequential voting does not approximate many common voting rules well even when the preferences are O-legal or separable. However, these paradoxes are much alleviated or even completely avoided when the preferences are lexicographic or represented by LP-trees. Our results thus draw a border for conditions under which sequential voting rules, which have extremely low com- putational and communicational cost, are good approximations of some common voting rules w.r.t. their corresponding scoring functions.

Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has recently been shown to be NP-complete, and thus of significantly lower complexity than unification in other DLs of similarly restricted expressive power. However, the unification algorithms for EL developed so far cannot deal with general concept inclusion axioms (GCIs). This paper makes a considerable step towards addressing this problem, but the GCIs our new unification algorithm can deal with still need to satisfy a certain cycle restriction.

This paper presents an axiomatic framework for influence diagram computation, which allows reasoning with partially ordered values of utility. We show how an algorithm based on sequential variable elimination can be used to compute the set of maximal values of expected utility (up to an equivalence relation). Formalisms subsumed by the framework include decision making under uncertainty based on multi-objective utility, or on interval-valued utilities, as well as a more qualitative decision theory based on order-of-magnitude probabilities and utilities.

In Belief Revision the new information is generally accepted, following the principle of primacy of update. In some case this behavior can be criticized and one could require that some new pieces of information can be rejected by the agent because, for instance, of insufficient plausibility. This has given rise to several approaches of non-prioritized Belief Revision. In particular (Hansson et al. 2001) defined credibility-limited revision operators, where a revision is accepted only if the new information is a formula that belongs to a set of credible formulas. They provide several representation theorems in the AGM style. In this work we study credibility-limited revision operators when the information is represented in propositional logic, like in the Katsuno and Mendelzon framework. We propose a set of postulates and a representation theorem for credibility-limited revision operators. Then we explore how to generalize these definitions to the Iterated Belief Revision case, using epistemic states in the Darwiche and Pearl style.