Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Attractor decompositions and their applications in games and automata

Prelegent: Marcin Jurdziński

2022-03-23 14:15

An attractor decomposition is a natural inductively defined decomposition of a graph that satisfies the parity condition, and its “shape” can be described by an ordered tree. The McNaughton-Zielonka algorithm implicitly produces an attractor decomposition of the winning set in a parity game. We argue that attractor decompositions and their trees can be used to measure the structural complexity of a winning strategy. We illustrate this on two examples: relating Lehtinen’s register number of a parity game to the smallest Strahler number of its attractor decomposition tree, and a quasi-polynomial translation from alternating parity automata on words to alternating weak automata.