The complexity of path-based defeasible inheritance

DOI10.1016/0004-3702(93)90081-LMaRDI QIDQ685542zbMATH OpenOpenAlexFDO

Publication date 19 January 1994

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(93)90081-l

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Knowledge representation (68T30)

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.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: The complexity of path-based defeasible inheritance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685542)