Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Is this Finite-State Transducer Sequentiable?
| |
|
Is this Finite-State Transducer Sequentiable?
Tamás Gaál6 
| (6) |
Grenoble Laboratory, Xerox Research Centre Europe, 6, chemin de Maupertuis, 38240 Meylan, France |
Abstract
Sequentiality is a desirable 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 ε-closure extension, is able to handle letter transducers
with arbitrary ε-ambiguities, too. Our algorithm is more economical than squaring, in terms 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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|