Transducers and the Power of Delay
Jeudi 18 janvier 2024, 14:00 à 15:00
Salle de séminaire du département informatique
(FEMTO, Université de Franche-Comté)
Transducers are theoretical machines computing functions: they read input words and answer with output words. Several variations of the standard transducer model have been developed to compute different classes of functions. This talk surveys three fundamental classes: Sequential functions, the basic class computed by the simplest model; Regular functions, a versatile class recognized by a variety of models; Polyregular functions, the most expressive but most complex class. The central theme of the talk is the notion of delay, a powerful tool that reduces problems about transducers to problems about automata.