Regular cost functions and stabilization monoids
14/03/2016 14 - 15 - 16 - 17 Março, sala 6.2.33 - DM - FCUL
Thomas Colcombet (LIAFA, Université Paris Diderot)
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 effectively equivalent: logic (cost monadic second-order logic), automata (Bautomata/
S-automata), expressions (B-rational expression/S-rational 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 effect 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.
14 | March | 15:30 – 17:30
15 | March | 9:30 – 11:30
16 | March | 16:00 – 18:00
17 | March | 10:30 – 12:30
|
