You are not logged in | Log in

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.