Defining rational functions by deterministic pushdown transducers

Speaker(s)

Maria Fraczak

Affiliation

Uniwersytet Warszawski

Date

Jan. 3, 2007, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Rational functions are partial functions from words to words. They are implemented by finite state automata extended to produce output; only some of them can be realized by deterministic pushdown transducers (deterministic pushdown automata producing output). I will present several classes of rational functions that can be realized by deterministic pushdown transducers of various kinds.

---