In previous work, we proposed a modal fragment of the situation calculus called ES, which fully captures Reiter's basic action theories. ES also has epistemic features, including only-knowing, which refers to all that an agent knows in the sense of having a knowledge base. While our model of only-knowing has appealing properties in the static case, it appears to be problematic when actions come into play. First of all, its utility seems to be restricted to an agent's initial knowledge base. Second, while it has been shown that only-knowing correctly captures default inferences, this was only in the static case, and undesirable properties appear to arise in the presence of actions.  In this paper, we remedy both of these shortcomings and propose a new dynamic semantics of only-knowing, which is closely related to Lin and Reiter's notion of progression when actions are performed and where defaults behave properly.

We develop a framework for forgetting concepts and roles (aka uniform interpolation) in terminologies in the lightweight description logic EL extended with role inclusions and domain and range restrictions. Three different notions of forgetting, preserving, respectively, concept inclusions, concept instances, and answers to conjunctive queries, with corresponding languages for uniform interpolants are investigated. Experiments based on SNOMED CT (Systematised Nomenclature of Medicine Clinical Terms) and NCI (National Cancer Institute Ontology) demonstrate that forgetting is often feasible in practice for large-scale terminologies.

On the other hand, the Recently, Ferraris, Lee and Lifschitz presented a solution provided by answer set programming (ASP), that is general definition of a stable model that is similar carried over to high level action language A [Gelfond and to the definition of circumscription, and can even Lifschitz, 1998] and many of its descendants that are based be characterized in terms of circumscription. In on ASP, uses both default negation (not) and strong negation this paper, we show the opposite direction, which ()--the idea of which is closely related to Reiter's default is, how to turn circumscription into the general stable logic solution [Reiter, 1980]. Interestingly, the development model semantics, and based on this, how to turn of the event calculus has spanned over both classical circumscriptive event calculus into answer set programs.

In this paper, we present a novel approach to the evaluation of propositional answer-set programs. In particular, for programs with bounded treewidth, our algorithm is capable of (i) computing the number of answer sets in linear time and (ii) enumerating all answer sets with linear delay. Our algorithm relies on dynamic programming, which so far has not been applied to ASP-problems. Therefore, our approach significantly differs from standard ASP-systems which implement techniques stemming from SAT or CSP, and thus usually do not exploit fixed parameter properties of the programs. We provide first experimental results which underline that, for programs with low treewidth, already a prototypical implementation is competitive compared to state-of-the-art systems.

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.

Knowledge-based recommenders support users in the identification of interesting items from large and potentially complex assortments. In cases where no recommendation could be found for a given set of requirements, such systems propose explanations that indicate minimal sets of faulty requirements. Unfortunately, such explanations are not personalized and do not include repair proposals which triggers a low degree of satisfaction and frequent cancellations of recommendation sessions. In this paper we present a personalized repair approach that integrates the calculation of explanations with collaborative problem solving techniques. In order to demonstrate the applicability of our approach, we present the results of an empirical study that show significant improvements in the accuracy of predictions for interesting repairs.

Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely limiting their practical utility. This paper presents a novel active testing approach based on MBD techniques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system description, computes a sequence of control settings for reducing the number of diagnoses. The approach complements probing, sequential diagnosis, and ATPG, and applies to systems where additional tests are restricted to setting a subset of the existing system inputs while observing the existing outputs. This paper evaluates the optimality of FRACTAL, both theoretically and empirically. FRACTAL generates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic information entropy. Further, the approximate sequence computed by FRACTAL's greedy approach is optimal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational circuits shows that FRACTAL reduces the number of remaining diagnoses according to a steep geometric decay function, even when only a fraction of inputs are available for active testing.

Recent results have shown the interest  of trees-of-BDDs as a suitable target language for propositional knowledge compilation from the practical side. In the present paper,  the concept of tree-of-BDDs is extended to additional classes of data structures C, thus leading to trees-of-C representations (ToC). We provide a number of generic results enabling one to determine the queries/transformations satisfied by ToC depending on those satisfied by C. We also present some results about the spatial efficiency of the ToC languages. Focusing on the ToB language (and other related languages), we address a number of issues that remained open in (Subbarayan et al 2007). We show that beyond co and va, the ToB fragment satisfies im and me but satisfies neither cd nor any query among ce, se unlesssf P = NP. Among other results, we prove that ToB is not comparable w.r.t. succinctness with any of cnf, dnf,  Dnnf unless the polynomial hierarchy collapses.This contributes to the explanation of  some empirical results reported in (Subbarayan et al 2007).

Current Answer Set Programming (ASP) solvers largely build on Datalog, which, unlike general logic programming, lacks function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e.g., lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive, but yet decidable, language that is useful, e.g., for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and some of their subclasses, addressing the main reasoning tasks. Our results also show that the recently introduced FDNC programs can be extended by inverse rules while retaining decidability, but computational costs are unavoidably higher.

We study the computational complexity of conjunctive query answering w.r.t. ontologies formulated in fragments of the description logic SHIQ. Our main result is the identification of two new sources of complexity: the combination of transitive roles and role hierarchies which results in 2ExpTime-hardness, and transitive roles alone which result in coNExpTime-hardness. These bounds complement the existing result that inverse roles make query answering in SHIQ 2ExpTime-hard.  We also show that conjunctive query answering with transitive roles, but without inverse roles and role hierarchies, remains in ExpTime if the ABox is tree-shaped.