Organizatorzy

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

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

7 maja 2008 14:15
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 …
30 kwietnia 2008 14:15
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 …
16 kwietnia 2008 14:15
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 …
2 kwietnia 2008 14:15
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 …
28 marca 2008 14:15
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 …
19 marca 2008 14:15
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 …
5 marca 2008 14:15
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 …
27 lutego 2008 14:15
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 …
16 stycznia 2008 14:15
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 …
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 …