The complexity of path-based defeasible inheritance (Q685542)

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.