No label defined (Q3830558)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4106303
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4106303 |
Statements
1989
0 references
default reasoning
0 references
model preference
0 references
complexity
0 references
0.9252871870994568
0 references
0.8459066152572632
0 references
[For the entire collection see Zbl 0668.68006.] Formal systems of NMR are undecidable in the first-order case and intractable in the propositional case. The aim of this paper is an investigation of limited but efficiently computable theories of default reasoning. A system of default reasoning is introduced in a purely semantic way. A model preference relation is defined: more preferred models are those in a sense generated from given models by means of default rules. Some types of default systems are introduced. The problem of finding a maximal model is of central importance in default systems. The complexity of finding a maximal model (with respect to the model preference relation) is studied. It is shown that: (1) The problem is NP- hard for the general propositional default system. (2) In the case of Horn theories there exists a linear algorithm. (3) Surprisingly, including the specificity condition into Horn theories leads to intractability. The specificity condition is necessary to overcome representational difficulties manifested by the existence of counterintuitive maximal models. (4) The problem in a theory consisting of Horn-form defaults (without specificity ordering) together with a set of Horn clauses is NP-hard (both propositional Horn-form default theories and Horn theories by themselves are linear). (5) There is a polynomial algorithm for the search problem in acyclic default Horn theories with specificity ordering. A correspondence between sets of model preference rules and standard default logic rules is shown.
0 references