Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

30 września 2010 14:15
- (Uniwersytet Warszawski)
holiday
2 czerwca 2010 14:15
Piotrek Hofman (Uniwersytet Warszawski)
time becomes data on the other side of the mirror
Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes …
26 maja 2010 14:15
Tibor Szabo (Freie Univeritaet Berlin)
Probabilistic intuition in positional games
19 maja 2010 14:15
Marek Grabowski (Uniwersytet Warszawski)
On simulation and trace inclusion
Simulation preorder and trace inclusion between transition systems asexamples of branching andlinear time problems. The talk will be devoted to the case when thetwo systems are given as a kindof product of finite-state ones. The …
12 maja 2010 14:15
Mr. Nobody (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
5 maja 2010 14:15
Tomasz Kazana (Uniwersytet Warszawski)
connection between cryptography and a pebble game
I will define a specific game in which a player puts pebbles on a board. Then I will show some properties of this game and connections with cryptrography.
28 kwietnia 2010 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Data monoids
A data monoid is like a monoid, but it is used to recognize languagesof data words, and not languages of words over finite alphabets. Iwill say what kind of languages of data words can be …
21 kwietnia 2010 14:15
Vince Barany (Rheinisch-Westfälische Technische Hochschule Aachen)
Querying the Guarded Fragment
Evaluating a boolean conjunctive query q over a guarded first-ordertheory T is equivalent to checking whether (T & not q) is unsatisfiable.This problem is relevant to the areas of database theory anddescription logic. Since q …
14 kwietnia 2010 14:15
Arnaud Carayol (Institut Gaspard-Monge)
Linear orderings in the pushdown hierarchy.
31 marca 2010 14:15
Mr. Nobody. (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
24 marca 2010 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
On topological complexity of MSO+U over infinite words
In [1] Bojańczyk considered WMSO+U logic and a new type of automata: max-automata. His main result is a conclusion that this logic is decidable over Ω. There arise the natural questions about expressive power of …
17 marca 2010 14:15
Clemens Ley (Oxford)
Towards effective characterizations of data languages.
We study the following decision problem. Given a deterministicregister automaton and a logic, decide if the language recognized bythe register automaton can be defined in the logic. This studyrequires new insights into deterministic register automata, …
10 marca 2010 14:15
Vaclav Brozek (Masaryk University)
Simple stochastic games on pushdown automata zoo
I will try to answer some suitable superset of the following questions: What the hell are simple stochastic games? Why should someone want to play it on pushdown automata? What are the natural habitats of …
3 marca 2010 14:15
Paweł Parys (Uniwersytet Warszawski)
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. (part 2)
A second order pushdown automaton is a pushdown automaton, which has a stack of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it has additional …
24 lutego 2010 14:15
Paweł Parys (Uniwersytet Warszawski)
Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata.
A second order pushdown automaton is a pushdown automaton, which has a stack of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it has additional …