Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Regular Talk: - Deterministic subsequential transducers with additional FIFO-memory
Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Deterministic subsequential transducers with additional FIFO-memory

Edit abstract data


Notice: Use of undefined constant session - assumed 'session' in /srv/www/htdocs-cs/cie08/conf-code.php on line 440

Notice: Use of undefined constant slot - assumed 'slot' in /srv/www/htdocs-cs/cie08/conf-code.php on line 441

Notice: Use of undefined constant room - assumed 'room' in /srv/www/htdocs-cs/cie08/conf-code.php on line 442
Speaker: Stefan Gerdjikov
Slot: Fri, 11:20-11:40, Amphitheater A (col. 1)

Abstract

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
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136
2008-05-19 Valid HTML 4.01! Valid CSS!