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