Nondeterminism in the Presence of a Diverse or Unknown Future

Prelegent(ci)

Denis Kuperberg

Afiliacja

Uniwersytet Warszawski

Termin

4 grudnia 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Udi Boker, Orna Kupferman, Michał Skrzypczak

Seminarium

Seminarium „Teoria automatów”

---

One of the advantages of deterministic automata is that they compose
well with trees and games. In the theory of cost functions, such
deterministic automata are not always available, so a weaker notion
was introduced: history-deterministic automata, which are
non-deterministic automata where nondeterminism can be resolved
depending only on the past (i.e. the prefix leading to the current
state).
The same notion was independently introduced under the name
Good-For-Games automata (GFG) by Henzinger and Piterman, leading to
simplified "determinization" procedure, where the resulting automaton
is GFG instead of deterministic.
In parallel, Kupferman Safra and Vardi (for X=Buchi), and later
Niwinski and Walukiewicz (for X=[i,j]-parity) showed that the derived
language der(L) of infinite trees with all branches in L is
recognizable by a X-nondeterministic tree automaton iff L is
recognizable by a X deterministic word automaton. In these works
however, there was an exponential blow-up between the tree automaton
and the deterministic automaton. In the same spirit as GFG automata,
we will say that a word automaton for L is Good-For-Trees (GFT), if it
can be used to recognized der(L) over trees.
We study here the connections between deterministic automata, GFT
automata, and GFG automata. We are in particular interested in the
complexity (in terms of number of states) of translation from one
formalism to another.

---