- ...
alphabet.
^{1} - If infinite alphabets are allowed, then certain
non-regular languages such as
can be recognized.
A similar generalization of regular languages is used by
[29].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
automata.
^{2} - Note that in such an implementation, the regular
expression operator ? (any symbol) is not to be confused with the
special symbol in automata
**?**(any symbol not occurring in the automaton).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... ?.
^{3} - Here we assume that we
are not explicitly representing states which are not co-accessible,
i.e. for which there is no path to a final state.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... transitions:
^{4} - An
implementation might choose to ignore transitions for which the
corresponding predicate is not satisfiable.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ....
^{5} - Note that without loss of generality we assume
that there is no separate input and output alphabet, nor separate
sets of predicates for input and output.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ....
^{6} - As is well-known, not all finite-state transductions
can be encoded by a deterministic transducer. As an example, a
transduction which maps every
`a`to a`b`if the input is of even length, and which maps every`a`to itself otherwise is a finite-state transduction, but cannot be encoded deterministically.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...roch:lang97.
^{7} - We
represent emissions associated with final states, as they surface in
the determinization algorithm below, using an extra transition with
as the domain part. We thus allow transitions
only in case
*q*is a final state and there are no transitions leaving*q*.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... deterministically:
^{8} - By `writing out
deterministically' we mean writing out with a deterministic state
transition. Such `deterministic' outputs may still in the end be
rejected if for some input, the machine ends in a non-final state.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... symbol.
^{9} - Of related interest is the
approach of [19]. He shows that
ambiguous transductions can be computed efficiently by factorizing
an ambiguous transducer
*T*into a functional transducer*T*_{1}and an ambiguous transducer*T*_{2}such that*T*is equivalent to , and such that*T*_{2}contains no `failing paths'. In typical cases,*T*_{1}contains meta-symbols which are expanded in*T*_{2}. This approach is more general in the sense that these meta-symbols range over sequences of symbols, rather than single symbols. It is more limited in the sense that identities cannot be expressed.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ...
Karttunen
^{10} - personal communication
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

- ... web-site.
^{11} `http://www.rxrc.xerox.com/research/mltt/fst/fsexamples.html`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .