Inconsistency detection device, inconsistency detection method, and computer-readable recording medium

An inconsistency detection method comprising:

• constructing a decision graph as a zero-suppressed binary decision diagram (ZDD) by representing results of case classification of values of logical expressions for variables based on a knowledge base as a binary decision tree and contracting the binary decision tree,
• wherein the decision graph comprises nodes corresponding to observed events and edges representing transition relationships between the nodes, and
• wherein the edges include a True edge corresponding to a transition in a case where a node is true and a False edge corresponding to a transition in a case where a node is false;
• for each accepted observed event, deleting an edge, from among the edges, that transitions to a negation side of an accepted observed event, wherein the deleted edge is one of the True edge or the False edge;
• after the deleting, setting a False label to a node for which no path to a true-valued leaf node exists at a final transition destination, and determining that no path to the true-valued leaf node exists in a case where the False label is set to a root node;
• extracting all paths in the decision graph from the root node to the true-valued leaf node after the deleting;
• assigning a respective path number to each of the extracted paths;
• detecting, among the extracted paths, one or more paths that satisfy a predetermined criterion including a path that includes an edge indicating a transition to a negation side of an observed event;
• adding, to each of one or more observed events associated with each detected path, the path number assigned to the detected path;
• deriving a minimal set of coverings of all path numbers added to the observed events;
• and
• deciding that the series of observed events is inconsistent with respect to the knowledge base in a case where it is determined that no path to the true-valued leaf node exists.

A non-transitory computer-readable recording medium storing an inconsistency detection program, which when executed by a processor, performs a method comprising:

• constructing a decision graph as a zero-suppressed binary decision diagram (ZDD) by representing results of case classification of values of logical expressions for variables based on a knowledge base as a binary decision tree and contracting the binary decision tree,
• wherein the decision graph comprises nodes corresponding to observed events and edges representing transition relationships between the nodes, and
• wherein the edges include a True edge corresponding to a transition in a case where a node is true and a False edge corresponding to a transition in a case where a node is false;
• for each accepted observed event, deleting an edge, from among the edges, that transitions to a negation side of an accepted observed event, wherein the deleted edge is one of the True edge or the False edge;
• after the deleting, setting a False label to a node for which no path to a true-valued leaf node exists at a final transition destination, and determining that no path to the true-valued leaf node exists in a case where the False label is set to a root node;
• extracting all paths in the decision graph from the root node to the true-valued leaf node after the deleting;
• assigning a respective path number to each of the extracted paths;
• detecting, among the extracted paths, one or more paths that satisfy a predetermined criterion including a path that includes an edge indicating a transition to a negation side of an observed event;
• adding, to each of one or more observed events associated with each detected path, the path number assigned to the detected path;
• deriving a minimal set of coverings of all path numbers added to the observed events;
• and
• deciding that the series of observed events is inconsistent with respect to the knowledge base in a case where it is determined that no path to the 1 true-valued leaf node exists.