Determinisation of History Deterministic Automata

Prelegent(ci)

Michał Skrzypczak

Afiliacja

Uniwersytet Warszawski

Termin

9 kwietnia 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

A non-deterministic automaton is history deterministic if it is possible to resolve its choices in a way that depends only on the already read input. Such automata appear naturally in synthesis problems and qualitative models.

One of the open problems about history deterministic automata is: what is the state-complexity of deteminisation of a given history deterministic omega-word parity automaton.

In this talk I will present the following results:
1) There exist co-Buchi history deterministic automata that do not admit any equivalent sub-exponential deterministic automata,
2) Every Buchi history deterministic automaton can be determinised without increasing the number of states.
Part of these results was obtained in cooperation with Denis Kuperberg.

---