** Next:** Finite State Transducers with
** Up:** Transducers with Predicates and
** Previous:** Determinization of Transducers

##

Determinization and identities

To treat identities, we must assume in the definition of
proto-transition that if one of
the positively occurring predicates in the boolean combination is
associated with an identity, then the resulting predicate
is associated with an identity as well. As an example consider the
following transducer. For simplicity we assume B and
C are mutually exclusive predicates; as before ? is a predicate which
is true of all symbols. Also, we write A:A for a transition A:A with an associated identity constraint.

Determinization produces:

Outputs associated with an identity are delayed like ordinary outputs.
Generalizing an idea due to Tamás Gaál and Lauri
Karttunen^{10} transducers with such
disconnected identities are interpreted as follows. During the
transduction of a string, a queue is maintained. Each time an input
symbol is matched by a predicate with an associated identity, this
symbol is enqueued. If a symbol matched by the corresponding predicate
on the output side has to be written, then that symbol is obtained by
a dequeue operation. With this use of a queue, our method for
interpreting a transducer is no longer finite state. The transducer
itself, however, still encodes a regular transduction.

A complication arises in cases like:

Determinization yields:

What sequence of output predicates should be put on the position of
the *? According to the
definitions, we get CE. However, this is not right because
then there is a path
which has an identity on the input side without a corresponding
identity on the output. Embedding such examples would
lead to transducers in which identities are `out of sync'. The
determinization algorithm is therefore extended by marking in the
output part that the scope of an identity ends; procedurally such a
mark is interpreted as a dequeue operation which ignores the dequeued
value. We write such a mark as
. In the
example the sequence of outputs X becomes
. In the definition of proto-transition, if at least one of the positively
occurring has an associated identity then we append a
mark to each of the outputs * Trans*
for which was not associated with an identity.

** Next:** Finite State Transducers with
** Up:** Transducers with Predicates and
** Previous:** Determinization of Transducers
*Noord G.J.M. van*

*2001-06-22*