Two-way pebble transducers for partial functions and their composition


Two-way finite state transducers are considered that use a finite number of pebbles, of which the life times must be nested. For every nondeterministic transducer that realizes a partial function, an equivalent deterministic transducer can be constructed. The composition of two deterministic transducers can be realized by one such transducer with a minimal number of pebbles.


0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)