We consider a simple language for writing causal action theories, and postulate several properties for the state transition models of these theories. We then consider some possible embeddings of these causal action theories in some other action formalisms, and their implementations in logic programs with answer set semantics. In particular, we propose to consider what we call permissible translations from these causal action theories to logic programs. We identify two sets of properties, and prove that for each set, there is only one permissible translation, under strong equivalence, that can satisfy all properties in the set. As it turns out, for one set, the unique permissible translation is essentially the same as Balduccini and Gelfond's translation from Gelfond and Lifschitz's action language B to logic programs. For the other, it is essentially the same as Lifschitz and Turner's translation from the action language C to logic programs. This work provides a new perspective on understanding, evaluating and comparing action languages by using sets of properties instead of examples. It will be interesting to see if other action languages can be similarly characterized, and whether new action formalisms can be defined using different sets of properties.

The goal of query conceptualization is to map instances in a query to concepts defined in a certain ontology or knowledge base. Queries usually do not observe the syntax of a written language, nor do they contain enough signals for statistical inference. However, the available context, i.e., the verbs related to the instances, the adjectives and attributes of the instances, do provide valuable clues to understand instances. In this paper, we first mine a variety of relations among terms from a large web corpus and map them to related concepts using a probabilistic knowledge base. Then, for a given query, we conceptualize terms in the query using a random walk based iterative algorithm. Finally, we examine our method on real data and compare it to representative previous methods. The experimental results show that our method achieves higher accuracy and efficiency in query conceptualization.

Instrumental variables (IVs) are widely used to identify causal effects. For this purpose IVs have to be exogenous, i.e., causally unrelated to all variables in the model except the explanatory variable X . It can be hard to find such variables. A generalized IV method has been proposed that only requires exogeneity conditional on a set of covariates. This leads to a wider choice of potential IVs, but is rarely used yet. Here we address two issues with conditional IVs. First, they are conceptually rather distant to standard IVs; even variables that are independent of X could qualify as conditional IVs. We propose a new concept called ancestral IV , which interpolates between the two existing notions. Second, so far only exponential-time algorithms are known to find conditional IVs in a given causal diagram. Indeed, we prove that this problem is NP-hard. Nevertheless, we show that whenever a conditional IV exists, so does an ancestral IV, and ancestral IVs can be found in polynomial time. Together this implies a complete and constructive solution to causal effect identification using IVs in linear causal models.

Existential rules (also known as Datalog+/- or tuple-generating dependencies) have been intensively studied in recent years as a prominent formalism in knowledge representation and database systems. We consider them here as a querying formalism, extending classical Datalog, the language of deductive databases. It is well known that the classes of databases recognized by (Boolean) existential rule queries are closed under homomorphisms. Also, due to the existence of a semi-decision procedure (the chase), these database classes are recursively enumerable. We show that, conversely, every homomorphism-closed recursively enumerable query can be expressed as an existential rule query, thus arriving at a precise characterization of existential rules by model-theoretic and computational properties. Although the result is very intuitive, the proof turns out to be non-trivial. This result can be seen as a very expressive counterpart of the prominent Lyndon-Los-Tarski-Theorem characterizing the homomorphism-closed fragment of first-order logic. Notably, our result does not presume the existence of any additional built-in structure on the queried data, such as a linear order on the domain, which is a typical requirement for other characterizations in the spirit of descriptive complexity.

We investigate fundamental properties of three-valued semantics for abstract dialectical frameworks (ADFs). In particular, we deal with realizability, i.e., the question whether there exists an ADF that has a given set of interpretations as its semantics. We provide necessary and sufficient conditions that hold for a set of three-valued interpretations whenever there is an ADF realizing it under admissible, complete, grounded, or preferred semantics. Moreover, we discuss how to construct such an ADF in case of realizability. Our results lay the ground for studying the expressiveness of ADFs under three-valued semantics. As a first application we study implications of our results on the existence of certain join operators on ADFs.

Trivia is any fact about an entity which is interesting due to its unusualness, uniqueness, unexpectedness or weirdness. In this paper, we propose a novel approach for mining entity trivia from their Wikipedia pages. Given an entity, our system extracts relevant sentences from its Wikipedia page and produces a list of sentences ranked based on their interestingness as trivia. At the heart of our system lies an interestingness ranker which learns the notion of interestingness, through a rich set of domain-independent linguistic and entity based features. Our ranking model is trained by leveraging existing user-generated trivia data available on the Web instead of creating new labeled data. We evaluated our system on movies domain and observed that the system performs significantly better than the defined baselines. A thorough qualitative analysis of the results revealed that our rich set of features indeed help in surfacing interesting trivia in the top ranks.

The sentential decision diagram (SDD) has been recently proposed as a new  tractable representation of Boolean functions that generalizes the influential  ordered binary decision diagram (OBDD).  Empirically, compiling CNFs into SDDs  has yielded significant improvements in both time and space over compiling  them into OBDDs, using a bottom-up compilation approach. In this work, we present a top-down CNF to SDD compiler that is based on techniques  from the SAT literature. We compare the presented compiler empirically to the state-of-the-art, bottom-up SDD compiler, showing orders-of-magnitude improvements in compilation time.

The AGM paradigm of belief change studies the dynamics of belief states in light of new information. Finding, or even approximating, dependent or relevant beliefs to a change is valuable because, for example, it can narrow the set of beliefs considered during belief change operations. Gärdenfors' preservation criterion (GPC) suggests that formulas independent of a belief change should remain intact. GPC allows to build dependence relations that are theoretically linked with belief change. Such dependence relations can in turn be used as a theoretical benchmark against which to evaluate other approximate dependence or relevance relations. There are already some studies, based on GPC, on the parallelism between belief change and dependence. One study offers a dependence relation parallel to AGM contraction for belief sets. Another study links base dependence relation to a more general belief base contraction, saturated kernel contraction. Here we offer yet a more general parallelism between kernel contraction and base dependence. At this level of generalization, different types of base dependence emerge. We prove that this differentiation of base dependence types is a result of possible redundancy in the base. This provides a theoretical means to distinguish between redundant and informative parts of a belief base.

Large formal mathematical knowledge bases encode considerable parts of advanced mathematics and exact science, allowing deep semantic computer assistance and verification of complicated theories down to the atomic logical rules. An essential part of automated reasoning over such large theories are methods learning selection of relevant knowledge from the thousands of proofs in the corpora. Such methods in turn rely on efficiently computable features characterizing the highly structured and inter-related mathematical statements.  In this work we (i) propose novel semantic features characterizing the statements in such large semantic knowledge bases, (ii) propose and carry out their efficient implementation using deductive-AI data-structures such as substitution trees and discrimination nets, and (iii) show that they significantly improve the strength of existing knowledge selection methods and automated reasoning methods over the large formal knowledge bases. In particular, on a standard large-theory benchmark we improve the average predicted rank of a mathematical statement needed for a proof by 22% in comparison with state of the art. This allows us to prove 8% more theorems in comparison with state of the art.

Computational models of argument could play a valuable role in persuasion technologies for behaviour change (e.g. persuading a user to eat a more healthy diet, or to drink less, or to take more exercise, or to study more conscientiously, etc). For this, the system (the persuader) could present arguments to convince the user (the persuadee). In this paper, we consider asymmetric dialogues where only the system presents arguments, and the system maintains a model of the user to determine the best choice of arguments to present (including counterarguments to key arguments believed to be held by the user). The focus of the paper is on the user model, including how we update it as the dialogue progresses, and how we use it to make optimal choices for dialogue moves.