BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Finite-state polynomial computation - Mikołaj Bojanczyk\, Univers
 ity of Warsaw
DTSTART:20220617T130000Z
DTEND:20220617T140000Z
UID:TALK175679@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION: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-t
 o-string functions.  For finite-state models\, such as finite automata\, t
 here is a difference\, and hence the study of string-to-string functions c
 omputed by automata\, also known as transducers\, is its own field.  \n\nE
 arly models of transducers where minor variations on automata. An example 
 of such a model is a Mealy machine\, which is a deterministic finite autom
 aton that produces one output letter in each transition. In time\, transdu
 cer 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 th
 eory is that\, similarly to the language case\, the important transducer m
 odels have many equivalent characterisations\, using automata\, logics\, a
 lgebra\, etc. \n\nIn this talk\, I would like to discuss such transducer m
 odels\, with an emphasis on those which compute string-to-string functions
  of polynomial growth. 
LOCATION:SS03
END:VEVENT
END:VCALENDAR