Two-way pebble transducers for partial functions and their composition
Two-way pebble transducers for partial functions and their composition
复制标题
部分功能双向卵石传感器及其组成
作者：
J. Engelfriet
双向有限状态换能器被认为使用有限数量的卵石，其中必须嵌套寿命。对于每个实现部分函数的非确定传感器，都可以构建等效的确定性传感器。两个确定性换能器的组成可以由一个这样的传感器实现，鹅卵石数量最少。
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.