Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Oberseminar / Stephan Barth, Representation of ω-regular Languages by Languages of Finite Words


Inhaltsbereich

Stephan Barth, Representation of ω-regular Languages by Languages of Finite Words

TCS Oberseminar, 06.07.2012, 14:15 Uhr im L109
Wann 14:15 15:15 06.07.2012
von bis
Wo L109
Termin übernehmen vCal
iCal

Stephan Barth
Representation of ω-regular Languages by Languages of Finite Words

There are several automata models for ω-regular languages, languages of infinite words. In all well-known models (Büchi, Parity, Rabin, Strett, Muller) minimization is NP-hard.

There is a lesser known model for representing omega-regular languages that performs better on this operation: Finite automata storing a finite word for every ultimate periodic word. Minimization algorithms for DFA can directly be applied, leading to minimization in O(n log n).

I will present this model with its already known transformations from and to Büchi automata and introduce algorithms for performing the most relevant operations (and, or, complement, projection) directly on this model.

Artikelaktionen

abgelegt unter:

Funktionsleiste