Nie jesteś zalogowany | Zaloguj się

Degrees of Ambiguity of Büchi Tree Automata

Prelegent(ci)
Alexander Rabinovich
Afiliacja
Tel Aviv University
Termin
10 kwietnia 2019 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countable) ambiguous if for every input it has at most finitely (respectively, countable) many accepting computations. An automaton is bounded ambiguous if there is k such that for every input it has at most k accepting computations.
We consider nondeterministic Büchi automata over infinite trees and prove that it is decidable in polynomial time whether an automaton is unambiguous, bounded ambiguous, finitely ambiguous, or countable ambiguous.