University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > Finite-state polynomial computation

Finite-state polynomial computation

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

  • UserMikołaj Bojanczyk, University of Warsaw
  • ClockFriday 17 June 2022, 14:00-15:00
  • HouseSS03.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity