Czekaj...Wczytywanie... Nie jesteś zalogowany | zaloguj się

## Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

• Skala szarości
• Wysoki kontrast
• Negatyw
• Reset

# Seminarium „Teoria automatów”

5050

## Lista referatów

• 2006-03-03, godz. 14:15, 5870

Emanuel Kieronski (Wroclaw, joint work with Martin Otto)

Logic with two variables and equivalence relations

We study first-order logic with two variables FO2 and establish a small substructure property. Similar to the small model property for FO2 we obtain an exponential size bound on embedded substructures, relative to a fixed surrounding structure that may be infinite. We apply this technique to analyse...

• 2006-02-22, godz. 14:15, 5870

Mikolaj Bojanczyk (Joint work with C. David, A. Muscholl, L. Segoufin and T. Schwentick. ) (Uniwersytet Warszawski)

Data words

A data word is a word that is annotated with data values. Every position in a data word has the usual label from a finite alphabet, but it also has a label from an infinite set. Access to the second coordinate - called the data value - is restricted. We present a decidable automaton model for data...

• 2006-01-18, godz. 14:15, 5870

Filip Murlak (Uniwersytet Warszawski)

Games for the Wadge Hierarchy of Deterministic Tree Languages

In the case of infinite words, the hierarchy of regular languages defined by continuous reductions is well understood since Wagner's 1977 paper. In particular, there exists a procedure calculating the exact level of a given language in the Wadge hierarchy. We will consider an analogous problem for t...

• 2005-12-14, godz. 14:15, 5870

Eryk Kopczynski (Uniwersytet Warszawski)

Half-positionally determined winning conditions in infinite games

We consider half-positionally determined winning conditions in infinite games played on a graph by two antagonistic players Eve and Adam. We call a winning condition W _positionally determined_ if, for every infinite game (G,W) using this winning condition, one of the players has a positional (i.e. ...

• 2005-12-07, godz. 14:15, 5870

Thomas Colcombet (Rennes) (Uniwersytet Warszawski)

Infnite games on finite graphs

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 number of turns, an infinite path has ...

• 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)

One-clock timed automata

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)

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...