Regular cost functions on finite words

Prelegent(ci)

Denis Kuperberg

Afiliacja

The Hebrew University of Jerusalem

Termin

15 maja 2013 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

The theory of regular cost functions, initiated by Thomas Colcombet and following work with Mikołaj Bojańczyk, is a satisfying framework to extend a large spectrum of results on regular languages to a quantitative setting. I will present the theory, and give an overview of the picture. We generalize a number of results from the theory of regular languages, often by showing equivalence between different formalisms (in terms of automata, logics, or semigroups). In particular we show that we can extend the notion of syntactic congruence to this quantitative framework. We also study the temporal class, which does not have a counterpart in language theory. This theory has also been developed on other structures: infinite words, finite trees and infinite trees.

---