Two-way pebble transducers for partial functions and their composition

Abstract

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.

Topics

0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)