Logical Approaches to Computational Barriers

Deterministic subsequential transducers with additional FIFO-memory

Speaker:
| Stefan Gerdjikov |

Slot: |
Array, 11:20-11:40, col. 1 |

Regular rewriting rules play a significant role in text-processing techniques. It is well known that they can be expressed in terms of rational functions and consequently for each such rule one can efficiently construct a transducer or, equivalently a bimachine. Unfortunately the transducers, in general, cannot be determinized and the bimachines do not allow to stream a text, and thus one cannot process a text on-line. We propose a new formalism, which aims at preserving the determinism and still to be able to process the input sequentially, i.e. whithout disposing on the entire text in advance. To this end we incorporate an additional infinite memory, represented as FIFO. We model it in a way to garantee the desired properties and to assure linear traversal of an input text. We call these machines \textit{FIFO-transducers} and study their properties with respect to rational functions. Our main efforts concern the composition problem. We shall that we can efficiently compose FIFO-transducers with subsequentional transducers, but in general they are not closed under composition and they are unable to describe the class of all rational function. We also show a simple example of function that is not rational but can be represented by such a machine. Finally, we define a subclass of rational functions that can be recognized by FIFO-transducers but (in the general case) not by a subsequenbtial transducer. We state sufficient conditions for a regular rule in order to be represented by a FIFO-transducer and show how to check these properties algorithmically.

websites: Arnold Beckmann | 2008-05-19 |