Cotygodniowe seminarium badawcze
2005-12-07, godz. 14:00, 2080
Thomas COLCOMBET (Uniwersytet w Rennes (Francja), CNRS)
Infinite games on finite graphs
Autorskie streszczenie wykladu: We consider games played on an arena (a graph) by two antagonistic players. In such a game, each player, when there is its turn, chooses an edge to follow, originating in the current position. The next position is the destination of this edge. After an infinite numb...
2005-11-30, godz. 14:15, 5870
Slawomir Lasota (Uniwersytet Warszawski)
For timed automata with two clocks emptyness in decidable but universality and containment are not. We will show that all these problems are decidable for alternating timed automata, but with only one clock. The non-primitive-recursive complexity will be shown. On infinite words, universality (and c...
2005-11-23, godz. 14:15, 5870
Slawomir Lasota (Uniwersytet Warszawski)
Complexity of bisimulation equivalence
An overview of known results and open problems in checking bisimulation equivalence on infinite graphs. In particular, graphs generated by context-free grammars and pushdown automata will be considered. Relationship to language equivalence will be pointed out, in particular for deterministic pushdow...
2005-11-18, godz. 14:15, 5870
Stephan Kreutzer (Uniwersytet Warszawski)
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)
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)
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)...