You are not logged in |
Determinisation of History Deterministic Automata
- Speaker(s)
- Michał Skrzypczak
- Affiliation
- Uniwersytet Warszawski
- Date
- April 9, 2014, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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.
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.
