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