The Experts below are selected from a list of 8853 Experts worldwide ranked by ideXlab platform
Meghyn Bienvenu - One of the best experts on this subject based on the ideXlab platform.
-
Prime implicates and prime implicants: from Propositional to modal logic
Journal of Artificial Intelligence Research, 2009Co-Authors: Meghyn BienvenuAbstract:Prime implicates and prime implicants have proven relevant to a number of areas of artificial intelligence, most notably abductive reasoning and knowledge compilation. The purpose of this paper is to examine how these notions might be appropriately extended from Propositional logic to the modal logic κ. We begin the paper by considering a number of potential definitions of clauses and terms for κ. The different definitions are evaluated with respect to a set of syntactic, semantic, and complexity-theoretic properties characteristic of the Propositional definition. We then compare the definitions with respect to the properties of the notions of prime implicates and prime implicants that they induce. While there is no definition that perfectly generalizes the Propositional notions, we show that there does exist one definition which satisfies many of the desirable properties of the Propositional Case. In the second half of the paper, we consider the computational properties of the selected definition. To this end, we provide sound and complete algorithms for generating and recognizing prime implicates, and we show the prime implicate recognition task to be Pspace-complete. We also prove upper and lower bounds on the size and number of prime implicates. While the paper focuses on the logic κ, all of our results hold equally well for multi-modal κ and for concept expressions in the description logic ALC.
Thomas Eiter - One of the best experts on this subject based on the ideXlab platform.
-
a logic programming approach to knowledge state planning semantics and complexity
arXiv: Artificial Intelligence, 2001Co-Authors: Thomas Eiter, Wolfgang Faber, Nicola Leone, Gerald Pfeifer, Axel PolleresAbstract:We propose a new declarative planning language, called K, which is based on principles and methods of logic programming. In this language, transitions between states of knowledge can be described, rather than transitions between completely described states of the world, which makes the language well-suited for planning under incomplete knowledge. Furthermore, it enables the use of default principles in the planning process by supporting negation as failure. Nonetheless, K also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special Case, which shows that the language is very flexible. As we demonstrate on particular examples, the use of knowledge states may allow for a natural and compact problem representation. We then provide a thorough analysis of the computational complexity of K, and consider different planning problems, including standard planning and secure planning (also known as conformant planning) problems. We show that these problems have different complexities under various restrictions, ranging from NP to NEXPTIME in the Propositional Case. Our results form the theoretical basis for the DLV^K system, which implements the language K on top of the DLV logic programming system.
-
default reasoning from conditional knowledge bases complexity and tractable Cases
Artificial Intelligence, 2000Co-Authors: Thomas Eiter, Thomas LukasiewiczAbstract:Abstract Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form “ φ→ψ ”, which informally read as “generally, if φ then ψ ”. Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default φ→ψ , does KB entail φ→ψ ? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general Propositional Case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore Cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.
-
On the computational cost of disjunctive logic programming: Propositional Case
Annals of Mathematics and Artificial Intelligence, 1995Co-Authors: Thomas Eiter, Georg GottlobAbstract:This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent is investigated for a variety of well-known semantics, as well as the complexity of deciding whether a Propositional formula is satisfied by all models according to a given semantics. We concentrate on finite Propositional disjunctive programs with as well as without integrity constraints, i.e., clauses with empty heads; the problems are located in appropriate slots of the polynomial hierarchy. In particular, we show that the consistency check is Σ _2 ^ p -complete for the disjunctive stable model semantics (in the total as well as partial version), the iterated closed world assumption, and the perfect model semantics, and we show that the inference problem for these semantics is Π _2 ^ p -complete; analogous results are derived for the answer sets semantics of extended disjunctive logic programs. Besides, we generalize previously derived complexity results for the generalized closed world assumption and other more sophisticated variants of the closed world assumption. Furthermore, we use the close ties between the logic programming framework and other nonmonotonic formalisms to provide new complexity results for disjunctive default theories and disjunctive autoepistemic literal theories.
Thomas Lukasiewicz - One of the best experts on this subject based on the ideXlab platform.
-
default reasoning from conditional knowledge bases complexity and tractable Cases
Artificial Intelligence, 2000Co-Authors: Thomas Eiter, Thomas LukasiewiczAbstract:Abstract Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form “ φ→ψ ”, which informally read as “generally, if φ then ψ ”. Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default φ→ψ , does KB entail φ→ψ ? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general Propositional Case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore Cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.
Varzinczak Ivan - One of the best experts on this subject based on the ideXlab platform.
-
Principles of KLM-style Defeasible Description Logics
'American College of Medical Physics (ACMP)', 2020Co-Authors: Britz Katarina, Casini Giovanni, Meyer Thomas, Moodley Kody, Sattler Uli, Varzinczak IvanAbstract:The past 25 years have seen many attempts to introduce defeasible-reasoning capabilities into a description logic setting. Many, if not most, of these attempts are based on preferential extensions of description logics, with a significant number of these, in turn, following the so-called KLM approach to defeasible reasoning initially advocated for Propositional logic by Kraus, Lehmann, and Magidor. Each of these attempts has its own aim of investigating particular constructions and variants of the (KLM-style) preferential approach. Here our aim is to provide a comprehensive study of the formal foundations of preferential defeasible reasoning for description logics in the KLM tradition. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann, and Magidor in the Propositional Case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and we investigate KLM-style syntactic properties for both preferen- tial and rational subsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our seman- tics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in description logics. Indeed, we also analyse the problem of non-monotonic reasoning in description logics at the level of entailment and present an algorithm for the computation of rational closure of a defeasible knowledge base. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible knowledge bases is no worse than that of reasoning in the underlying classical DL ALC
-
On the Decidability of a Fragment of preferential LTL
HAL CCSD, 2019Co-Authors: Varzinczak Ivan, Cheikh Fahima, Condotta Jean-françois, Chafik AnasseAbstract:International audienceLinear Temporal Logic (LTL) has found extensive applications in Computer Science and Artificial Intelligence, notably as a formal framework for representing and verifying computer systems that vary over time. Non-monotonic reasoning, on the other hand, allows us to formalize and reason with exceptions and the dynamics of information. The goal of this paper is therefore to enrich temporal formalisms with non-monotonic reasoning features. We do so by investigating a preferential semantics for defeasible LTL along the lines of that extensively studied by Kraus et al. in the Propositional Case and recently extended to modal and description logics. The main contribution of the paper is a decidability result for a meaningful fragment of preferential LTL that can serve as the basis for further exploration of defeasibility in temporal formalisms
-
Theoretical Foundations of Defeasible Description Logics
2019Co-Authors: Britz Katarina, Casini Giovanni, Meyer Thomas, Moodley Kody, Sattler Uli, Varzinczak IvanAbstract:We extend description logics (DLs) with non-monotonic reasoning features. We start by investigating a notion of defeasible subsumption in the spirit of defeasible conditionals as studied by Kraus, Lehmann and Magidor in the Propositional Case. In particular, we consider a natural and intuitive semantics for defeasible subsumption, and investigate KLM-style syntactic properties for both preferential and rational subsumption. Our contribution includes two representation results linking our semantic constructions to the set of preferential and rational properties considered. Besides showing that our semantics is appropriate, these results pave the way for more effective decision procedures for defeasible reasoning in DLs. Indeed, we also analyse the problem of non-monotonic reasoning in DLs at the level of entailment and present an algorithm for the computation of rational closure of a defeasible ontology. Importantly, our algorithm relies completely on classical entailment and shows that the computational complexity of reasoning over defeasible ontologies is no worse than that of reasoning in the underlying classical DL ALC.Comment: 60 page
Grigori Schwarz - One of the best experts on this subject based on the ideXlab platform.
-
autoepistemic logic and introspective circumscription
Theoretical Aspects of Rationality and Knowledge, 1994Co-Authors: Michael Gelfond, Vladimir Lifschitz, Halina Przymusinska, Grigori SchwarzAbstract:We investigate the relationship between two epistemic nonmonotonic formalisms: autoepistemic logic and introspective circumscription. Finitely axiomatized autoepistemic theories are shown to be equivalent to the Propositional Case of introspective circumscription. This theorem is applied to the problem of relating the usual "minimizing" circumscription to autoepistemic logic.
