A short course by Thomas Colcombet (LIAFA, Université Paris Diderot).
14 March | 15h30-17h30
15 March | 9h30-11h30
16 March | 16h00-18h00
17 March | 10h30-12h30
Abstract: 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 (B-automata/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.
