Is this finite-state transducer sequentiable ?
Sequentiality is a deisrable property of finite state transducers : such transducers are optimal for time
efficiency. Not all transducers are sequentiable. Sequentialization algorithms of finite state transducers do not
recognize whether a transducer is sequentiable or not and simply do not ever halt when it is not. Choffrut
proved that sequentiality of finite state transducers is decidable. Béal et al. have proposed squaring to decide
sequentiality. We propose a different procedure, which, with e-disclosure extension, is able to handle letter
transducers with arbitrary e-ambiguities, too. Our algorithm is more economical than squaring, in termas of
size. In different cases of non-sequentiability necessary and sufficient conditions of the ambiguity class of the
transducer can be observed. These ambiguities can be mapped bijectively to particular basic patterns in the
structure of the transducer. These patterns can be recognized, using finite state methods, in any transducer.
Proc. 6th Int. Conf. On Implementation and Application of Automata (CIAA 2001), Pretoria, South Africa, 23-25 July, 2001.
Is-this-finite-state-transducer-sequentiable.pdf (140.61 kB)