Finite-state polynomial computation

Add to your list(s) Download to your calendar using vCal

• Mikołaj Bojanczyk, University of Warsaw
• Friday 17 June 2022, 14:00-15:00
• SS03.

If you have a question about this talk, please contact Jamie Vicary.

For powerful computational models, such as Turing machines, or polynomial time Turing machines, it does not make much of a difference if one considers string-to-Boolean functions (i.e. languages) or string-to-string functions. For finite-state models, such as finite automata, there is a difference, and hence the study of string-to-string functions computed by automata, also known as transducers, is its own field.

Early models of transducers where minor variations on automata. An example of such a model is a Mealy machine, which is a deterministic finite automaton that produces one output letter in each transition. In time, transducer models have grown in sophistication, and now they are powerful enough to resemble programming languages, with features such as loops or higher-order functions. At the same time, because they are “finite-state”, the halting problem remains decidable. An appealing part of transducer theory is that, similarly to the language case, the important transducer models have many equivalent characterisations, using automata, logics, algebra, etc.

In this talk, I would like to discuss such transducer models, with an emphasis on those which compute string-to-string functions of polynomial growth.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• SS03
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.