Regular cost functions and stabilization monoids
15/03/2016 March,14 to 17, Room 6.2.33
Thomas Colcombet (LIAFA, Univ. Paris Diderot)
ShortCourse
Regular cost functions form a quantitative extension to the classical notion of regular languages. However, contrary to other models, it focuses only on boundedness questions. Hence, cost functions are maps from words to ? ∪ ∞, which are considered modulo ‘preservation of bounds’. The resulting theory resembles a lot the one for regular languages. In particular, many models of acceptors are e?ectively equivalent: logic (cost monadic secondorder logic), automata (Bautomata/Sautomata), expressions (Brational expression/Srational expressions), and algebra (stabilisation monoids).
In this course, we will introduce some of these objects, present the central results and the remaining open problem. We will be paying a particular attention to the algebraic formalism of stabilisaiton monoids. Stabilisation monoids are ordered monoids enriched with a map from idempotents to idempotents which essentially represents the e?ect of iterating a large (unbounded) number of times the element. We will see how associating semantics to these objects. We will also show how these can be used in ‘la Schützenberger’ algebraic characterization results yielding important decidable subclasses.
Schedule (Room 6.2.33)
14  March  15:30 – 17:30
15  March  9:30 – 11:30
16  March  16:00 – 18:00
17  March  10:30 – 12:30
FCUL  Departamento de Matemática  Edifício C6.
