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

May 7, 2008, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Eliminating randomness from infinite games
Consider infinite games played on a graph by two antagonistic players Eve and Adam. Each position in the game graph belongs to one of two players, who decides which move he or she takes; the …
April 30, 2008, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
What is a regular language of data words?
It is impossible to define an automaton model for data words that would simultaneously satisfy several reasonable requirements, such as closure under boolean operations, decidable emptiness, etc. I will present some attempts that have appeared …
April 16, 2008, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
XPath evaluation in linear time
We consider a fragment of XPath where attribute values can only be tested for equality (FOXPath). We show that for any fixed unary query in this fragment, the set of nodes that satisfy the query …
April 2, 2008, 2:15 p.m.
Sybille Froeschle (Oldenburg) (Uniwersytet Warszawski)
The Insecurity Problem: Tackling Unbounded Data
In this talk we focus on tackling the insecurity problem of security protocols in the presence of an unbounded number of data such as nonces or session keys. First, we pinpoint four open problems in …
March 28, 2008, 2:15 p.m.
Christof Loeding (Aachen) (Uniwersytet Warszawski)
The nondeterministic Mostowski hierarchy and distance-parity automata
The number of priorities that nondeterministic Mostowski or parity automata on infinite trees can use in their acceptance condition induces a hierarchy of regular tree languages. This talk is about the problem of deciding for …
March 19, 2008, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Property testing regular languages
Property testing is concerned with the following type of problems: Let L be a property of a class of objects. A property tester for L is an algorithm, which, given an input object w, uses …
March 5, 2008, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
Lossy Machines
FIFO- and counter-automata are Turing complete models. I will present a weakening of these models, allowing for spontaneous and non-controllable loss of messages from FIFO (or, respectively, decrements of counters). I will discuss how much …
Feb. 27, 2008, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
Weak index versus Borel rank
I will talk about weak recognizability of deterministic languages of infinite trees. I will prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, I will propose a procedure computing …
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 …