Organizers

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

Information

Wednesdays, 2:15 p.m. , room: 5440

Research fields

List of talks

Sept. 30, 2010, 2:15 p.m.
- (Uniwersytet Warszawski)
holiday
June 2, 2010, 2:15 p.m.
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 …
May 26, 2010, 2:15 p.m.
Tibor Szabo (Freie Univeritaet Berlin)
Probabilistic intuition in positional games
May 19, 2010, 2:15 p.m.
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 …
May 12, 2010, 2:15 p.m.
Mr. Nobody (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
May 5, 2010, 2:15 p.m.
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.
April 28, 2010, 2:15 p.m.
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 …
April 21, 2010, 2:15 p.m.
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 …
April 14, 2010, 2:15 p.m.
Arnaud Carayol (Institut Gaspard-Monge)
Linear orderings in the pushdown hierarchy.
March 31, 2010, 2:15 p.m.
Mr. Nobody. (Neverland)
There won't be seminar, this wednesday.
Holiday :-).
March 24, 2010, 2:15 p.m.
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 …
March 17, 2010, 2:15 p.m.
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, …
March 10, 2010, 2:15 p.m.
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 …
March 3, 2010, 2:15 p.m.
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 …
Feb. 24, 2010, 2:15 p.m.
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 …