Workshop on the theory of regular cost functions, and beyond

Friday 21 September afternoon, Berlin

Satellite event of Highlights of Logic, Games, and Automata

Organised by Laure Daviaud, Nathanaël Fijalkow, and Denis Kuperberg

Here is the programme



The theory of regular cost functions is a quantitative extension of the theory of rational languages. Languages (which can be viewed as Boolean functions on words) are replaced by functions, which map words to natural integers and are characterized by boundedness properties. Automata, rational expressions, MSO logic and syntactic monoids have all their counterparts in the theory of regular cost functions.

The study was initiated by Thomas Colcombet in the 2009 ICALP paper showing an exact correspondence between B-automata (and S-automata), cost-MSO, and stabilisation monoids. This was inspired by works of Hashiguchi, Leung, Simon, and Kirsten and related to more recent works by Bojańczyk, Colcombet, and Löding, to study the star-height problem and more generally so-called ''boundedness problems'' (e.g. boundedness of distance automata).

The theory of regular cost functions blossomed in the past 10 years, leading to new insights with applications in automata theory, games, logic, and database theory. The goal of this workshop is to survey some of the results and to discuss new research directions.