Show simple item record

Complexity, Decidability and Undecidability Results for Rule- Based Expert Systems

dc.contributor.authorBlanksteen, Scotten_US
dc.contributor.authorHendler, James A.en_US
dc.contributor.authorNau, Dana S.en_US
dc.description.abstractWe prove the equivalence of domain-independent planning systems and rule-based expert systems. We use this equivalence to examine how the complexity of deriving conclusions in rule-based expert systems depends on the nature of the rules. We show conditions under which conclusion derivation is decidable and undecidable. For those cases where the problem is decidable, we show how the time complexity varies depending on a wide variety of conditions: whether or not function symbols are allowed; whether or not rules may retract facts; whether or not negative conditions are allowed; whether or not the rules are allowed to take arguments; and whether the rules are given as part of the input to the expert system, or instead are fixed in advance.en_US
dc.format.extent757835 bytes
dc.relation.ispartofseriesISR; TR 1992-117en_US
dc.subjectcomputational complexityen_US
dc.subjectexpert systemsen_US
dc.subjectSystems Integrationen_US
dc.titleComplexity, Decidability and Undecidability Results for Rule- Based Expert Systemsen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record