Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

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

Seminarium „Teoria automatów”

Cotygodniowe seminarium badawcze

Lista referatów

  • 2005-11-18, godz. 14:15, 5870

    Stephan Kreutzer (Uniwersytet Warszawski)

    DAG-width and Parity Games

    Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm development. Tree-width is characterised by a game known as the cops-and-robber game where a number of cops chase a robber on the gr...

  • 2005-11-02, godz. 14:15, 5870

    Hugo Gimbert (joint work with Wieslaw Zielonka)

    Positional Payoff Games

    I will present some results about the existence of positional optimal strategies in two-players antagonistic games and of positional Nash equilibria in multiplayer games...

  • 2005-10-19, godz. 14:15, 5870

    Damian Niwinski (joint work with T. Knapik, P. Urzyczyn, and I. Walukiewicz) (Uniwersytet Warszawski)

    Model checking of panic automata

    Panic automata, invented by Pawel Urzyczyn, extend the concept of 2nd order pushdown automata (with stacks of stacks), by a destructive move called panic. They are in a sense equivalent to 2nd order tree grammars. We show the decidability, in fact, 2-EXPTIME-completeness, of the Mu-calculus model-ch...

  • 2005-10-05, godz. 14:15, 5870

    Mikolaj Bojanczyk (joint with Igor Walukiewicz) (Uniwersytet Warszawski)

    Unranked Tree Algebra

    I will present an algebra for recognizing languages of unranked, finite trees. This algebra is a special case of a transformation semigroup. The talk will focus on analyzing algebras that correspond to languages defined in logic (for instance, first-order logic)...