Only knowing captures the intuitive notion that the beliefs of an agent are precisely those that follow from its knowledge base. While only knowing has a simple possible-world semantics in a single agent setting, the many agent case has turned out to be much more challenging. In a recent paper, we proposed an account which arguably extends only knowing to multiple agents in a natural way. However, the approach was limited in that the semantics cannot deal with infinitary notions such as common knowledge. In this work, we lift that serious limitation to obtain a first-order language with only knowing and common knowledge, allowing us to study the interaction between these notions for the very first time. By adding a simple form of public announcement, we then demonstrate how the muddy children puzzle can be cast in terms of logical implications given what is only known initially.

We introduce epistemic quantified boolean logic (EQBL), an extension of propositional epistemic logic with quantification over propositions. We show that EQBL can express relevant properties about agents’ knowledge in multi-agent contexts, such as “agent a knows as much as agent b”. We analyse the expressiveness of EQBL through a translation into monadic second-order logic, and provide completeness results w.r.t. various classes of Kripke frames. Finally, we prove that model checking EQBL is PSPACE-complete. Thus, the complexity of model checking EQBL is no harder than for (non-modal) quantified boolean logic.

Stream reasoning is the task of continuously deriving conclusions on streaming data. To get results instantly one evaluates a query repeatedly on recent data chunks selected by window operators. However, simply recomputing results from scratch is impractical for rule-based reasoning with semantics similar to Answer Set Programming, due to the trade-off between complexity and data throughput. To address this problem, we present a method to efficiently update models of a rule set. In particular, we show how an answer stream (model) of a LARS program can be incrementally adjusted to new or outdated input by extending truth maintenance techniques. We obtain in this way a means towards practical rule-based stream reasoning with nonmonotonic negation, various window operators and different forms of temporal reference.

In this paper we combine two of the most important areas of knowledge representation, namely belief revision and (abstract) argumentation. More precisely, we show how AGM-style expansion and revision operators can be defined for Dung's abstract argumentation frameworks (AFs). Our approach is based on a reformulation of the original AGM postulates for revision in terms of monotonic consequence relations for AFs. The latter are defined via a new family of logics, called Dung logics, which satisfy the important property that ordinary equivalence in these logics coincides with strong equivalence for the respective argumentation semantics. Based on these logics we define expansion as usual via intersection of models. We show the existence of such operators. This is far from trivial and requires to study realizability in the context of Dung logics. We then study revision operators. We show why standard approaches based on a distance measure on models do not work for AFs and present an operator satisfying all postulates for a specific Dung logic.

The adoption of a generic contrariness notion in ASPIC+ substantially enhances its expressiveness with respect to other formalisms for structured argumentation. In particular, it opens the way to novel investigation directions, like the use of multivalued logics in the construction of arguments. This paper points out however that in the current version of ASPIC+ a serious technical difficulty related with generic contrariness is present. With the aim of preserving the same level of generality, the paper provides a solution based on a novel notion of closure of the contrariness relation at the level of sets of formulas and an abstract representation of conflicts between sets of arguments. The proposed solution is shown to satisfy the same rationality postulates as ASPIC+ and represents a starting point for further technical and conceptual developments in structured argumentation.

We consider existential rules (aka Datalog +/-) as a formalism for specifying ontologies. In recent years, many classes of existential rules have been exhibited for which conjunctive query (CQ) entailment is decidable. However, most of these classes cannot express transitivity of binary relations, a frequently used modelling construct. In this paper, we address the issue of whether transitivity can be safely combined with decidable classes of existential rules. First, we prove that transitivity is incompatible with one of the simplest decidable classes, namely aGRD (acyclic graph of rule dependencies), which clarifies the landscape of ‘finite expansion sets’ of rules. Second, we show that transitivity can be safely added to linear rules (a subclass of guarded rules, which generalizes the description logic DL-LiteR) in the case of atomic CQs, and also for general CQs if we place a minor syntactic restriction on the rule set. This is shown by means of a novel query rewriting algorithm that is specially tailored to handle transitivity rules. Third, for the identified decidable cases, we pinpoint the combined and data complexities of query entailment.

Baader et al., 2013; Borgwardt et al., 2013; Özcep et al., 2013; Klarman and Meyer, 2014] and shown to preserve query Aiming at ontology-based data access over temporal, rewritability. Note, however, that the inability to define temporal in particular streaming data, we design a language of predicates such as Blizzard(x, t) in ontologies leaves the ontology-mediated queries by extending OWL 2 QL burden of encoding them within queries to the user, which and SPARQL with temporal operators, and investigate goes against the OBDA paradigm. Moreover, natural queries rewritability of these queries into two-sorted such as'check if a weather station has been serviced every 24 first-order logic with and PLUS over time.

In this paper, we propose to use the language of bidirectional constraints to specify schema mappings in the context of data exchange. These constraints impose restrictions over both the source and the target data, and have the potential to minimize the ambiguity in the description of the target data to be materialized. We start by making a case for the usefulness of bidirectional constraints to give a meaningful closed-world semantics for st-tgds, which is motivated by Clark's predicate completion and Reiter's formalization of the closed-world assumption of a logical theory. We then formally study the use of bidirectional constraints in data exchange. In particular, we pinpoint the complexity of the existence-of-solutions and the query evaluation problems in several different scenarios, including in the latter case both monotone and non-monotone queries.

Query answering under existential rules — implications with existential quantifiers in the head — is known to be decidable when imposing restrictions on the rule bodies such as frontier-guardedness [Baget et al., 2010; Baget et al., 2011a]. Query answering is also decidable for description logics [Baader, 2003], which further allow disjunction and functionality constraints (assert that certain relations are functions); however, they are focused on ER-type schemas, where relations have arity two. This work investigates how to get the best of both worlds: having decidable existential rules on arbitrary arity relations, while allowing rich description logics, including functionality constraints, on arity-two relations. We first show negative results on combining such decidable languages. Second, we introduce an expressive set of existential rules (frontier-one rules with a certain restriction) which can be combined with powerful constraints on arity-two relations (e.g. GC2, ALCQIb) while retaining decidable query answering. Further, we provide conditions to add functionality constraints on the higher-arity relations.

This paper relates two extensively studied formalisms: abstract dialectical frameworks and logic programs with generalized atoms or similar constructs. While the syntactic similarity is easy to see, also a strong relation between various stable model semantics proposed for these formalisms is shown by means of a unifying framework in which these semantics are restated in terms of program reducts and an immediate consequence operator, where program reducts have only minimal differences. This approach has advantages for both formalisms, as for example implemented systems for one formalism are usable for the other, and properties such as computational complexity do not have to be rediscovered. As a first, concrete result of this kind, one stable model semantics based on program reducts and subset-minimality that reached a reasonable consensus for logic programs with generalized atoms provides a novel, alternative semantics for abstract dialectical frameworks.