Information Technology Reference
In-Depth Information
present some preliminary notions. In Section 3, we define first-order and monadic
second-order logics interpreted on finite words, and define MSO-transducers, for
which we give several examples. In Section 4, we introduce the main state-based
models of transformations used in this paper. In Section 5, we present the main
transducer-logic connection for transformations of finite words. Finally in Section
6, we briefly survey some extensions of the finite word setting.
2 Word Transformations
We define the preliminary notions used all over this paper.
Words
An
alphabet ʣ
is a finite set of symbols, called letters. A
word w
over
ʣ
is
a finite sequence of letters (
˃
1
,...,˃
n
), denoted
w
=
˃
1
...˃
n
. The empty word
(empty sequence) is denoted by
.The
length
of a non-empty word
w
=
˃
1
...˃
n
is defined by
|} ↆ
N
∗
|
w
|
=
n
,and
|
|
=0.Wedenotebydom(
w
)=
{
1
,...,
|
w
the domain of
w
.Inparticular,dom(
)=
dom(
w
),
i
is called a
position
of
w
and
w
(
i
) denotes the
i
-th letter of
w
. The set of words over
ʣ
is
denoted by
ʣ
∗
, while the set of non-empty words over
ʣ
is denoted by
ʣ
+
.
Given two words
w
1
=
˃
1
...˃
n
and
w
2
=
ʲ
1
...ʲ
m
,their
concatenation
,
denoted
w
1
.w
2
(or simply
w
1
w
2
), is defined by
w
1
.w
2
=
˃
1
...˃
n
ʲ
1
...ʲ
m
.In
particular,
w
=
w
=
w
for all words
w
∅
. For all
i
∈
ʣ
∗
. For all
w
ʣ
∗
and
n
,we
denote by
w
n
the concatenation of
w
,
n
times. In particular,
w
0
=
,
w
1
=
w
and
w
2
=
ww
.
∈
∈
∈
N
Transformations
A
transformation R
of finite words over an alphabet
ʣ
is a
binary relation over
ʣ
∗
, i.e.
R
ʣ
∗
,welet
R
(
u
)
be the set of images of
u
by
R
, i.e.
R
(
u
)=
{v ∈ ʣ
∗
|
(
u,v
)
∈ R}
.Theword
u
is usually called an
input word
while the words
v
such that (
u,v
)
∈ R
are
called
output words
.Wedenotebydom(
R
) the domain of
R
, and by range(
R
)
its range, i.e. dom(
R
)=
ʣ
∗
×
ʣ
∗
. For all words
u
ↆ
∈
ʣ
∗
|
ʣ
∗
|∃
{
u
∈
R
(
u
)
=
∅
}
and range(
R
)=
{
v
∈
u
∈
ʣ
∗
,v
.
A transformation
R
is
functional
if
R
is a function, i.e. for all words
u
∈
R
(
u
)
}
ʣ
∗
,
∈
the cardinality of
R
(
u
) is smaller than or equal to 1, i.e.
1. Functional
transformations are rather denoted by
f,g,h...
. For a functional transformation
f
,wewrite
f
(
u
)=
v
instead of
f
(
u
)=
|
R
(
u
)
|≤
{
v
}
, for all (
u,v
)
∈
f
.
Example 1.
Let
ʣ
=
. The following examples of (functional) transforma-
tions of finite words over
ʣ
are running examples in this paper.
{
a, b
}
-
The transformation
f
del
:
ʣ
∗
→
ʣ
∗
deletes all letters
a
, i.e. for all input
words
u
=
˃
1
...˃
n
,
f
del
(
u
)=
˃
i
1
...˃
i
k
such that
{
i
1
<
···
<i
k
}
=
{
i
∈
. E.g.
f
del
(
abaabb
)=
bbb
.
-
The transformation
f
double
doubles every input letter, i.e. for all
u
=
˃
1
...˃
n
,
f
double
(
u
)=
˃
1
˃
1
...˃
n
˃
n
, e.g.
f
double
(
abaa
)=
aabbaaaa
.
dom(
w
)
|
w
(
i
)
=
a
}
