Organizers

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

Information

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

Research fields

List of talks

Jan. 16, 2008, 2:15 p.m.
Aymeric Vincent (Uniwersytet Warszawski)
Mec 5 and AltaRica
In this presentation, we will present the Mec 5 verification tool and its environment. In particular, we will talk about the AltaRica formalism which has been developed in Bordeaux for more than ten years. We …
Jan. 9, 2008, 2:15 p.m.
Leszek Kolodziejczyk (Uniwersytet Warszawski)
The polynomial and linear time hierachies in a weak theory of arithmetic
I will show that a very weak theory of arithmetic associated with the complexity class AC^0 does not prove that the polynomial time hierarchy is equal to the linear time hierarchy. The proof uses Ajtai's …
Nov. 28, 2007, 2:15 p.m.
Andrzej Nagorko (Uniwersytet Warszawski)
Automatic groups, continued
Nov. 21, 2007, 2:15 p.m.
Wieslaw Zielonka
Games with priorities
Nov. 14, 2007, 2:15 p.m.
Andrzej Nagorko (Uniwersytet Warszawski)
Automatic groups
I'll talk about automatic groups, which incorporate finite state automata into geometric group theory in a prolific way. The class of automatic groups was introduced by Cannon and Thurston in the eighties.
Nov. 7, 2007, 2:15 p.m.
Mikolaj Bojanczyk (Uniwersytet Warszawski)
Automata and logics for data values
An XML document is commonly modeled as a tree, with nodes labeled by a finite alphabet. Properties of such documents can be expressed using finite tree automata, which are well understood and admit efficient algorithms. …
Oct. 24, 2007, 2:15 p.m.
Wojciech Czerwinski (Uniwersytet Warszawski)
Simulation between games
I will show some results of my investigations on bisimulation with a weakened winning condition for Spoiler. I will present a polynomial algorithm deciding this (modified) bisimulation between Buchi games. I will also talk about …
Oct. 17, 2007, 2:15 p.m.
Balder ten Cate (joint work with J. van Benthem and J. Vaananen) (Uniwersytet Warszawski)
Lindstrom theorems for fragments of first-order logic
Lindstrom theorems characterize logics in terms of model-theoretic conditions such as Compactness and the Loewenheim-Skolem property. Most existing Lindstrom theorems concern extensions of first-order logic. On the other hand, many logics relevant to computer science …
Oct. 10, 2007, 2:15 p.m.
Hugo Gimbert (joint work with F. Horn) (Uniwersytet Warszawski)
Algorithms for Solving Simple Stochastic Games
A Simple Stochastic Game is played by two players called Min and Max, moving turn by turn a pebble along edges of a graph. Player Max wants the pebble to reach a special vertexc called …
May 30, 2007, 2:15 p.m.
Paweł Parys (joint work with Krzysztof Onak) (Uniwersystet Warszawski)
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders
We extend the binary search technique to searching in trees. We consider two models of queries: questions about vertices and questions about edges. We present a general approach to this sort of problem, and apply …
May 23, 2007, 2:15 p.m.
Anna Niewiarowska (Uniwersytet Warszawski)
Probalistically Checkable Proofs and approximation hardness (continued)
May 16, 2007, 2:15 p.m.
Artur Jeż (Uniwersytet Warszawski)
Conjunctive grammars
I discuss the notion of conjunctive grammars, introduced by A. Okhotin in 2001. In short they can be described as extension of context-free grammars with additional operation of intersection within the body of any production. …
May 9, 2007, 2:15 p.m.
Anna Niewiarowska
Probalistically Checkable Proofs and approximation hardness
The PCP theorem states that for each NP language there is a verifier that checks membership proofs probabilistically, using only logaritmic number of random bits and reading constant number of proof bits. I will show …
April 25, 2007, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Forest expressions
I will talk about a type of regular expression for unranked trees. The main focus is on connections with logic: the expressions correspond to chain logic, the star-free expressions correspond to first-order logic, and finally, …
April 18, 2007, 2:15 p.m.
Konrad Zdanowski (Uniwersytet Warszawski)
Undecidability methods for the word problem in finite semigroups