Information Technology Reference
In-Depth Information
input
word
1
2
3
4
5
6
7
8
a
a
a
a
b
b
b
b
copy 1
a
a
a
a
b
b
b
b
b
b
b
b
a
a
a
a
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
(a) Transformation
f
del
defined by
T
del
input
word
1
2
3
4
5
6
7
8
a
b
a
a
b
b
b
a
copy 1
a
a
a
a
b
b
b
b
b
b
b
b
a
a
a
a
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
1
,
2
φ
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
φ
2
,
1
copy 2
a
a
a
a
b
b
b
b
a
b
a
a
b
b
b
a
(b) Transformation
f
double
defined by
T
double
input
word
1
2
3
4
5
6
7
8
a
a
a
a
b
b
b
b
copy 1
a
a
a
a
b
b
b
b
b
b
b
b
a
a
a
a
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
2
φ
1
,
2
copy 2
a
a
a
a
b
b
b
b
b
b
b
b
a
a
a
a
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
φ
2
,
2
(c) Transformation
f
copy
defined by
T
copy
input
word
1
2
3
4
5
6
7
8
a
a
a
a
b
b
b
b
copy 1
a
a
a
a
b
b
b
b
b
b
b
b
a
a
a
a
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
(d) Transformation
f
rev
defined by
T
rev
input
word
1
2
3
4
5
6
7
8
a
a
a
a
a
a
a
a
copy 1
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
φ
1
,
1
(e) Transformation
f
1
/
2
defined by
T
1
/
2
Fig. 1.
Transformations of Example 1 defined by MSO-transducers
•
The transformation
f
rev
is defined by the transducer
T
rev
: it suces to take
only one copy of the input structure and to inverse the order relation. Formally,
T
rev
is defined by
k
= 1 and:
ˆ
L
a
(
x
)=
L
a
(
x
)
ˆ
L
b
(
x
)=
L
b
(
x
)
ˆ
1
,
1
ˆ
pos
(
x
)
ˆ
dom
≡
≡
(
x, y
)
≡
y
x
