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

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
April 3, 2007, 2:15 p.m.
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 …
March 21, 2007, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Temporal Logics and Model Checking for Fairly Correct Systems
I will present recent results on model checking for fairly correct systems (D. Varacca, H. Voelzer, LICS'06). A fair variant of a specfication is obtained by replacing "for all paths" by "for a large set …
March 14, 2007, 2:15 p.m.
Pawel Parys (Uniwersytet Warszawski)
On Systems of Equations Satisfied in All Commutative Finite Semigroups
I show the algorithmic procedure for solving the problem: check if a system of equations has a solution in every commutative finite semigroup.