Information Technology Reference
In-Depth Information
Property 3.1
In a positive cycle, if
≠
relation does not exist between any two
nodes, then all nodes denotes the same variables in this cycle.
Property 3.2
There exists a positive cycle in a inequality graph, if there exists
≠
relation between any two nodes in the cycle, then inequality graph contains
inconsistency.
Property 3.1 can be used to carry on equivalent transformation on inequality
graph to make it exclude positive cycle. The method is merging all nodes of
positive cycle into one single node according to unit sharing strategy for all
positive cycle of graph. Result graph obtained is called reduced inequality graph.
Property 3.2 can be used to define inconsistency of inequality graph.
Definition 3.2
One inequality graph is inconsistent, if and only if in this graph
there exists a edgee, in which some two variable nodes have “
”relation.
Theorem 3.1
One inequality graph is inconsistent, if and only if in its reduced
graph , there exist one edge with“
”relation from one variable node to itself.
Base on these two facts, the inequality reasoner carries on graph traversal. If a
positive cycle is found out, then use unit sharing strategy to merge the cycle into
one variable node. If one variable's domain is null or one variable has one ≠
relation pointed to itself, then report the inconsistency. It is easy to prove the
completeness of operations described above for partial order relation and
identical relation. Given a set
including identical relation, inequality relation
and partial order relation, and the set
W
G
of axiom about identical relation and
partial order relation, then
W
∪
G
is inconsistent if and only if inequality graph
corresponding to
is inconsistent.
Compared with deductive method, graph operation method is much more
effective. Because the graph traversal has linear complexity.
W
3.10.4
Inequality Reasoning
The inequality graph reflects structural characteristic of inequality. When the
variable node in the inequality graph is limited by interval, besides operation of
inequality graph, constraints propagate in the inequality graph. All these
operations are caused after inequality graph receives an outside input. The
outside inputs include adding a relation expression
x
r
y
into the network, where
x
and
are variables or constants, but at least one variable; r is one of relations =,
≠, <, ≤, >, ≥.
y
