this paper reports on systematic research which aims to classify non-monotonic logics by their expressive power. the classification is based on translation functions that satisfy three important criteria: polynomialit...
详细信息
ISBN:
(纸本)3540667490
this paper reports on systematic research which aims to classify non-monotonic logics by their expressive power. the classification is based on translation functions that satisfy three important criteria: polynomiality, faithfulness and modularity (PFM for short). the basic method for classification is to prove that PFM translation functions exist (or do not exist) between certain logics. As a result, non-monotonic logics can be arranged to form a hierarchy. this paper gives an overview of the current expressive power hierarchy (EPH) and investigates semi-normal default logic as well as prerequisite-free and semi-normal default logic in order to locate their exact positions in the hierarchy.
Recent research in answer-set programming (ASP) is concerned withthe problem of finding faithful transformations of logic programs under the stable semantics. this is in particular relevant in practice when programs ...
详细信息
ISBN:
(纸本)9783540721994
Recent research in answer-set programming (ASP) is concerned withthe problem of finding faithful transformations of logic programs under the stable semantics. this is in particular relevant in practice when programs with variables are considered, where such transformations play a basic role in (offline) simplifications of logic programs. So far, such transformations of non-ground programs have been considered under the implicit assumption that the domain (i.e., the set of constants of the underlying language) is always suitably extensible. However, this may not be a desired scenario, e.g., if one needs to deal with a fixed number of objects. In this paper, we investigate how an explicit restriction of the domain influences the applicability of program transformations and we study in detail computational aspects for the concepts of tautological rules and rule sub-sumption. More precisely, we provide a full picture of the complexity to decide whether a non-ground rule is tautological or subsumed by another rule under several restrictions.
We introduce an approach to preferences suitable for agents that base decisions on their beliefs. In our work, agents' preferences are perceived as a consequence of their beliefs, but at the same time are used to ...
详细信息
ISBN:
(纸本)9783642405648
We introduce an approach to preferences suitable for agents that base decisions on their beliefs. In our work, agents' preferences are perceived as a consequence of their beliefs, but at the same time are used to feed the knowledge base with beliefs about preferences. As a result, agents can reason with preferences to hypothesize, explain decisions, and review preferences in face of new information. Finally, we integrate utility-based to reasoning-based criteria of decision making.
We present a declarative language, PP, for the specification of preferences between possible solutions (or trajectories) of a planning problem. this novel language allows users to elegantly express non-trivial, multi-...
详细信息
the recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its...
详细信息
ISBN:
(纸本)9783540721994
the recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eliyahu and Dechter, that can still be turned into nondisjunctive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that generalize earlier results on HCF programs. Given an HEF program, we provide an algorithm for finding an elementary set whose loop formula is not satisfied, which has a potential for improving stable model computation by answer set solvers.
Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations. we have access to genotype data (genetic ...
详细信息
ISBN:
(纸本)9783642042379
Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. However, due to technological limitations. we have access to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure. Withthese biological motivations, we Study haplotype inference-determining the haplotypes that form a given set of genotypes-using Answer Set programming we call our approach HAPLO-ASP. this note summarizes the range of problems that can be handled by HAPLO-ASP, and its applicability and effectiveness on real data in comparison withthe other existing approaches.
Although knowing the operating systems running in a network is becoming more and more important (mainly for security reasons), current operating system discovery tools are not sufficiently accurate to acquire the info...
详细信息
ISBN:
(纸本)9783642042379
Although knowing the operating systems running in a network is becoming more and more important (mainly for security reasons), current operating system discovery tools are not sufficiently accurate to acquire the information in a fully automated way. Many design choices explain this lack of accuracy, but they all come down to a poor knowledge representation scheme. In this paper, we study how answer set programming call he used to guide the design of a knowledge-oriented operating system discovery tool. the result is significantly more accurate than today's state of the art tools.
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explici...
详细信息
ISBN:
(纸本)3540667490
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explicit negation to the default negation of normal programs in order to distinguish what can be shown to be false from what cannot be proven true. Annotated logic programs generalize the set of truth values over which a program is interpreted by explicitly annotating atoms with elements of a new domain of truth values. In this paper coherent well-founded annotated programs are defined, and shown to generalize both consistent and paraconsistent extended programs, along with several classes of annotated programs.
Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed point logic (FPL) extension of C...
详细信息
ISBN:
(纸本)3540285385
Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed point logic (FPL) extension of Clark's completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (loosely) guarded programs. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed point logic (mu(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling a characterization of an answer set semantics by mu LGF formulas. Finally, we relate guarded OASP to Datalog LITE, thus linking an answer set semantics to a semantics based on fixed point models of extended stratified Datalog programs. From this correspondence, we deduce 2-EXPTIME-completeness of satisfiability checking w.r.t. (loosely) guarded programs.
Problems arising from the revision of propositional knowledge bases have been intensively studied for two decades. Many different approaches to revision have thus been suggested, withthe ones by Dalal or Satoh being ...
详细信息
ISBN:
(纸本)9783642042379
Problems arising from the revision of propositional knowledge bases have been intensively studied for two decades. Many different approaches to revision have thus been suggested, withthe ones by Dalal or Satoh being two of the most fundamental ones. As is well known, most computational tasks in this area are intractable. therefore, in practical applications, one requires Sufficient conditions under which revision problems become efficiently solvable. In this paper, we identify such tractable fragments for the reasoning and the enumeration problem exploiting the notion of treewidth. More specifically, we present new algorithms based on dynamic programming for these problems in Dalal's setting and a tractability Proof using Courcelle's theorem for Satoh's approach.
暂无评论