Transducers with polynomial size increase

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Feb. 14, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

For functional string-to-string transductions, one of the most popular models is deterministic two-way automata with output. This model admits many different equivalent characterisations (mso transductions, streaming string transducers), and strictly generalises other transducer models such as the sequential or rational functions.

Deterministic two-way automata with output have at most linear size increase – i.e. the output size is at most linear in terms of the input size. In this talk, I will discuss a class of string-to-string functions which has polynomial size increase. I will argue that this class is very robust, and can be characterised in at least four different ways, using: pebble transducers, mso interpretations, compositions of certain basic building blocks, and a fragment of the \lambda calculus. Functions from this class can also be evaluated efficiently (e.g. in AC^0), and I conjecture that the equivalence problem is decidable.

---