Nie jesteś zalogowany |
Transducers with polynomial size increase (part 2)
- Prelegent(ci)
- Mikołaj Bojańczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 21 lutego 2018 14:15
- Pokój
- p. 5050
- Seminarium
- Seminarium „Teoria automatów”
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.
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.
