BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:
A survey on regular cost-functions and their applications
STATUS:CONFIRMED
ATTENDEE;CN="Thomas Colcombet
":
MAILTO:no@spam.com
DESCRIPTION:
This talk will be the occasion to give an introduction to re
gular cost-functions\, to describe the main concepts involve
d\, to give an overview of the known results and open proble
ms\, and to show some applications. The theory of regular co
st-functions offer a quantitative extension to the notion of
regular language. Regular cost-functions can count\, for in
stance the number of occurrence of some patterns\, and can o
ptimize quantities (for instance compute nested infima and s
uprema). In particular\, some notions of resource consumptio
n can be easily expressed using regular cost-functions. Regu
lar cost-functions can be used over words\, finite of infini
te\, or trees\, finite or infinite (though infinite trees ar
e only partially understood so far). As it is the case for r
egular languages\, this theory comes with several decision p
rocedures and many forms of effectively equivalent computati
onal models such as automata (B-automata and S-automata)\, a
lgebra (stabilisation monoids)\, expressions (B-expressions
and S-expressions)\, or logics (cost-monadic second-order lo
gic). These results strictly extend their classical language
counterparts. The theory of regular cost-functions continue
s and uses the techniques and results developed formerly by
Hashiguchi\, Leung\, Simon and Kirsten since the early eight
ies. At the same it provides a uniform and more general fram
ework for understanding all these works. The central questio
n addressed by regular cost-functions is the ability to deci
de the existence of a bound on the range of some finitely re
presented function. On the one hand\, only concentrating on
bounds may be seen as a severe restriction (but otherwise\,
decidability would be immediately lost). On the other hand\,
many problems in computer science\, or in mathematics turn
out to be reducible to questions of existence of bounds on s
ome quantities. For this reason\, several non-trivial proble
ms can be shown decidable by reduction to cost-function deci
sion procedures. Let us cite for instance the finite power p
roperty (given a regular language L\, does there exist n suc
h that L^n=L*)\, the star height problem (given a regular la
nguage L and an integer k\, is it possible to write L as a r
egular expression using at most k nesting of Kleene stars) a
nd its extension to trees\, the finite substitution problem\
, the problem of finitely unfolding fixpoints of MSO formula
e while preserving their semantics\, some quantitative varia
nts of the Church synthesis problem\, or the decidability of
the Rabin-Mostowski hierarchy (a problem only partially sol
ved so far).
DTSTART;TZID=Europe/Paris:20131203T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=201312031
100
UID:LSVsemLSV.201312031100@lsv.ens-cachan.fr
LOCATION:Salle de ConfĂ©rence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR