Information Technology Reference
In-Depth Information
of output delay , which have been used, for instance, to make elegant proofs of
the decidability of equivalence of functional FST [7].
Recently introduced by M. Bojanczyk, a stronger semantics have been given
to transformations, that takes into account the origin of the output letters in
the input word. Several classical problems have been revisited and most of them
become trivial with this new semantics [9]. Some problems, still open in the
classical semantics, have also been solved in the origin semantics, such as getting
a machine-independent characterisation of MSO-transformations, as well as an
effective characterisation of first-order transformations. We present some of these
new results in this section.
ʣ . An origin function for v in
Definition 3. Let ʣ be an alphabet, and u,v
u is a mapping o :dom( v )
dom( u ) . A word transformation with origin over
ʣ is a set of pairs ( u, ( v, o )) such that u,v
ʣ and o is an origin function for
v in u.
Intuitively, o ( i ) is the position in the input word at which the position i of
the output word has been produced. Origin semantics can be defined for the
transducer models we have seen so far. For instance, the origin transformation
(or o -transformation) defined by an FST T is the set of pairs, denoted by
T
o ,
of the form ( u, ( v, o )) such that ( u,v )
dom( v ), o ( i )the
position of u where T has produced v ( i ), i.e. where T has triggered a transition
on reading u ( o ( i )) which has produced a partial word containing the letter v ( i ).
With this semantics, the origin equivalence problem for FST, i.e. deciding
whether two FST T 1 ,T 2 satisfy
T
,andforall i
o , can be easily solved, because T 1
and T 2 can be seen respectively as two automata A 1 ,A 2 over ʣ
T 1
o =
T 2
ʣ k ,where k
is the longest output word occurring on the transitions of T 1 and T 2 . Indeed,
×
o iff the automata A 1 and A 2 are equivalent, i.e., define the same
language. This trick, however, cannot be used for two-way FST, making origin
semantics more interesting in this context.
It is also possible to give a natural origin semantics to transformations realised
by MSO-transducers T .Inthatcase,( u, ( v, o )) T o if ( u,v ) T o and, if i c
is the k -th node of v (wrt to
T 1
T 2
o =
), where i
dom( u )and c is a copy, then we let
o ( k )= i .
In the origin world, it is possible to characterise algebraically first-order de-
finable transformations with origin, while this problem is open in the classical
setting. Moreover, this characterisation is effective when the transformation is
defined by, say, an MSO-transducer.
Let u
ʣ , o :dom( u )
N
,and X
N
. The abstraction u/ X of u by X is
the word over ʣ := ʣ
∪{↥}
obtained by replacing in u each letter at position
i
is a fresh symbol not in ʣ . For instance,
if u = aba with origin o (1) = 3, o (2) = 2 and o (3) = 1, then u/ { 2 , 3 } =
dom( u )by
if o ( i )
X ,where
↥↥
a .
the equivalence relation on ʣ
We let
induced by the equation
=
↥↥
.
E.g.
a .
Given an o -transformation f , one defines its reverse rev ( f ). For all u
a
b
↥↥
a
↥↥↥
b , but a
ʣ ,if
( v, o )= f ( u ), then rev ( f )=( f rev ( v ) ,rev ( o )), where rev ( o )( i )= o (
|
v
|−
i +1).
 
Search WWH ::




Custom Search