Information Technology Reference
In-Depth Information
a
˃ ∈ ʣ
U
:=
V
V
:=
Ua
U
:=
U˃
V
:=
V˃
˃
U
:=
U˃
˃
U
:=
˃U
a | U
:=
Ua
q
0
q
1
q
0
q
0
q
0
q
0
a | U
:=
U
U
U
U
UUV
UUU
U
(a)
f
1
/
2
(b)
f
1
/
2
(c)
f
copy
(d)
f
copy
(e)
f
rev
Fig. 5.
Examples of streaming string transducers
Fig. 5(b). The function
f
copy
can be defined with one or two registers, as depicted
by Fig. 5(c) and Fig. 5(d). Finally,
f
rev
is defined by the SST of Fig. 5(e). Un-
like MSO-transformations, SST-definable transformations may not be linear-size
increase, as shown by the SST of Fig.4 which defines the transformation
f
exp
.
To capture MSO-transformations, various syntactic restrictions on SST register
updates have been defined in several papers [2,3,4,6], which can be defined as
restrictions of a uniform notion of
transition monoids
for SSTs [26], as presented
in the next section.
4.4 Transition Monoids for Streaming String Transducers
ʣ
∗
,
that represent the state and variable flow of the SST over
w
[26]. Let
T
=
(
Q,q
0
,ʴ,
The transition monoid of an SST is a set of matrices
M
w
, for all words
w
∈
X
,ˁ,O
) be an SST over an alphabet
ʣ
, let two states
q
1
,q
2
∈
Q
,two
ʣ
∗
and
n
registers
U
1
,U
2
∈X
0,
the pair (
q
1
,U
1
)
n
-flows to (
q
2
,U
2
) on reading
w
if there exists a run of
T
on
w
from
q
1
to
q
2
, on which the sequence of register updates makes
U
1
contributes
n
times to the content of
U
2
. The pair (
q
1
,U
1
)
,aword
w
∈
∈
N
∪ {↥}
. Intuitively, if
n
≥
-flow to (
q
2
,U
2
) if there is no
run on
w
from
q
1
to
q
2
. For example, for the SST of Fig. 5(a), (
q
0
,U
)1-flowsto
(
q
1
,U
) on reading
a
,aswellas
a
k
for all odd integers
k
. On Fig. 5(b), (
q
0
,U
)
1-flows to (
q
0
,V
) on reading
a
.OnFig.4,(
q
0
,U
)2
k
-flows to (
q
0
,U
) on reading
a
k
for all
k
↥
0.
Formally, (
q
1
,U
1
)
n-flows to
(
q
2
,U
2
)on
w
(
n
≥
0), denoted (
q
1
,U
1
)
w
n
(
q
2
,U
2
),
if there exists a run
r
of
T
on
w
, from state
q
1
to state
q
2
, such that
U
1
occurs
n
times in
s
r
(
U
2
), where
s
r
is the substitution defined by
r
. The pair (
q
1
,U
2
)
≥
↥
-
flows to (
q
2
,U
2
) if there is no run of
T
on
w
, from state
q
1
to state
q
2
.Wedenote
by
M
w
the (
N
∪{↥}
)-valued square matrices of dimension
|Q|.|X|
defined, for
all
q
1
,q
2
∈
Q
and all
U
1
,U
2
∈X
,andall
n
∈
N
∪{↥}
,by
M
w
[
q
1
,U
1
][
q
2
,U
2
]=
n
iff (
q
1
,U
1
)
w
n
(
q
2
,U
2
)
Definition 2 (SST Transition Monoid).
The transition monoid of an SST
T is the set of matrices M
(
T
)=
{M
w
| w ∈ ʣ
∗
}.
