Organizatorzy

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

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

9 stycznia 2008 14:15
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 …
28 listopada 2007 14:15
Andrzej Nagorko (Uniwersytet Warszawski)
Automatic groups, continued
21 listopada 2007 14:15
Wieslaw Zielonka
Games with priorities
14 listopada 2007 14:15
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.
7 listopada 2007 14:15
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. …
24 października 2007 14:15
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 …
17 października 2007 14:15
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 …
10 października 2007 14:15
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 …
30 maja 2007 14:15
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 …
23 maja 2007 14:15
Anna Niewiarowska (Uniwersytet Warszawski)
Probalistically Checkable Proofs and approximation hardness (continued)
16 maja 2007 14:15
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. …
9 maja 2007 14:15
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 …
25 kwietnia 2007 14:15
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, …
18 kwietnia 2007 14:15
Konrad Zdanowski (Uniwersytet Warszawski)
Undecidability methods for the word problem in finite semigroups
3 kwietnia 2007 14:15
Damian Niwiński (Uniwersytet Warszawski)
Two remarks on the role of ranks in parity games
These observations are of very different nature, but they can be read as evidences for the lower bound, and the upper bound, respectively. At first we show that the number of ranks gives rise to …