Information Technology Reference
In-Depth Information
˃ ∈ ʣ | ˃,
+1
˃ ∈ ʣ | ˃,
+1
|,
+1
|,
+1
q
0
q
1
q
0
q
1
˃ ∈ ʣ | ˃,
+1
|, −
1
|, −
1
|,
+1
q
3
q
2
q
2
|
˃ ∈ ʣ | , −
1
˃ ∈ ʣ | ˃, −
1
|
(a)
f
copy
(b)
f
rev
Fig. 3.
Examples of two-way finite state transducers
a
U
:=
UU
be a finite set of registers denoted by the cap-
ital letters
U,V,W...
and
ʣ
be an alphabet. A sub-
stitution
s
is defined as a mapping
s
:
Let
X
a
U
:=
aa
)
∗
.
X→
(
ʣ
∪X
q
0
q
1
ʣ
∗
.
A valuation is defined as a substitution
v
:
X→
Let
S
X,ʣ
be the set of all substitutions. Any substi-
tution
s
canbeextendedto
s
:(
ʣ
)
∗
in a straightforward manner. The composition
s
1
s
2
of
two substitutions
s
1
and
s
2
is defined as the standard
function composition
s
1
ⓦ
)
∗
→
∪X
(
ʣ
∪X
U
U
Fig. 4.
SST for
f
exp
s
2
.
A
streaming string transducer
(SST) over
ʣ
is a
tuple
T
=(
Q,q
0
,ʴ,
X
,ˁ,O
)where
Q
is a finite set of states with initial state
q
0
;
ʴ
:
Q
×
ʣ
→
Q
is a transition function;
X
is a finite set of registers;
ˁ
:
ʴ
→S
X,ʣ
X
∗
is a (partial) output function.
Like FST, a
run r
of an SST
T
is an alternating sequence of states and letters
r
=
p
0
˃
1
p
1
...˃
n
p
n
such that
p
0
=
q
0
and for all
i
is a register update function; and
O
:
Q
∈{
0
,...,n
−
1
}
,
ʴ
(
p
i
,˃
i
+1
)is
defined and equal to
p
i
+1
.Therun
r
is
accepting
if
p
n
∈
=
n
the length of
r
. In particular, a run of length 1 follows exactly one transition.
The sequence
dom(
O
). We let
|
r
|
s
r,i
0
≤i≤|r|
of substitutions induced by
r
is defined inductively
as:
s
r,
0
is the identity function over
X
,and
s
r,i
=
s
r,i−
1
ˁ
(
p
i−
1
,˃
i
)for1
≤
i
≤|
r
|
.
We denote
s
r,|r|
by
s
r
.
If the run
r
is accepting, we can extend the output function
O
to the run
r
by
O
(
r
)=
s
s
r
(
O
(
p
n
)), where
s
substitutes all registers by their initial value
.
As for FST and 2FST, the functional transformation
defined by an SST
T
is the set of pairs (
u,v
) such that there exists an accepting run
r
of
T
on
u
such that
v
=
O
(
r
).
T
Example 6.
The definition of SST is best understood with some examples. Any
FST can be encoded as an SST with a single register. As an example, consider
the SST that defines the function
f
1
/
2
in Fig. 5(a). It has only one register
U
. The register update substitutions are represented on the edges by the the
assignment operator :=, while the output function is represented by the ver-
tical arrows leading to an expression, here
U
. The function
f
1
/
2
can also be
defined with only one state, but using one additional register
V
, as depicted by
