The complexity of path-based defeasible inheritance
type: Item
instance of: scholarly article
title: The complexity of path-based defeasible inheritance
zbMATH Open document ID: 0779.68080
DOI: 10.1016/0004-3702(93)90081-L
author: Bart Selman
author: Hector J. Levesque
published in: Artificial Intelligence
publication date: 1994-01-19T00:00:00Z
review text: Inheritance networks are used for representing taxonomic information. For instance, common knowledge about adult students can be expressed by network with nodes \{Jill, student, adult, adult student, employed\} with positive edges \(Jill\to adult student\), \(adult student\to student\), \(adult student\to adult\), \(adult\to employed\) and with a negative edge \(student \nrightarrow employed\). A network may have several conclusion sets (minimal sets of edges which are obtained by concatenation and which are not contradicted or preempted), e.g. the above set of edges \(\Gamma\) has two such exensions: \(\Gamma\cup \{J\to as\to a\to e,J\to as\to a,J\to as\to s,as\to a\to e\}\) and \(\Gamma\cup \{J\to as\to s\nrightarrow e,J\to as\to a,J\to as\to s,as\to s\nrightarrow e\}\) (so called credulous grounded extensions, proposed by Touretyky). It is shown that calculation of the conclusion set using any version of downward inheritance is NP-hard; however, upward inheritance is tractable.
reviewed by: Jaak Henno
Mathematics Subject Classification ID: 68T27
Mathematics Subject Classification ID: 68T30
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 417433
zbMATH Keywords: non-monotone logic
zbMATH Keywords: Inheritance
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
cites work: Q3200586
cites work: Q3888567
cites work: Q4198056
cites work: A skeptical theory of inheritance in nonmonotonic semantic networks
cites work: Q3493327
cites work: Hard problems for simple default logics
cites work: Q3829532
cites work: On finding a minimum dominating set in a tournament
cites work: Q5578545
cites work: Some representational issues in default reasoning
cites work: Q3200596
cites work: Q3992826
full work available at URL: 0004-3702(93)90081-l
OpenAlex ID: W2051000181
description: scientific article; zbMATH DE number 417433