Regular cost functions and stabilization monoids

Short-Course

  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 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 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.