Information Technology Reference
In-Depth Information
c0
f
R
R
f
S
R
S
R
g
R
c0
f
g
R
v
v
f
t
t
c0
v
v
f
f
t
t
Fig. 3. Compression , Selection 1 and Selection 2 graph transformation rules
Selection 2 reduces the number of constants of
by one. The final state of a
derivation describes a DAG labeled by constants of Σ only, that does not contain
cycles of S edges, and, represents a convergent rewrite system over Σ .
K
5Examp s
Example 1. Figure
4
a)
presents
the
construction
of
DAG ( E ),
where
E
=
{f ( f ( f ( a )))
≈ a, f ( f ( a ))
≈ a, g ( c, c )
≈ f ( a ) ,g ( c, h ( a ))
≈ g ( c, c ) ,c≈
h ( a ) ,b≈ m ( f ( a ))
}
.
K
=
{c 1 ,...,c 10 }
. We apply all the following mandatory
transformations on
DAG ( E ) in a certain order constructing the order on the
constants of
“on the fly.” Orient orients the E edge between c 1 and c 4 into an
R edge from c 4 to c 1 ( c 4 c 1 ), and the E edge between c 1 and c 3 into an R edge
from c 1 to c 3 ( c 1 c 3 ). We can apply an SR transformation that replaces the
S edge from c 2 to c 3 by an S edge from c 2 to c 1 .Let c 2 c 4 .Wemerge c 2 and
c 4 ; c 2 is removed from the graph, the S
K
edges between c 2 and c 3 are removed,
Search WWH ::

Custom Search