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

Oct. 17, 2008, 2:15 p.m.
Thomas Wilke (Kiel)
and other Modal) Logics in Information Securit
Oct. 8, 2008, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Max-regular languages
A new class of languages of inﬁnite words is introduced, called the max-regular languages, extending the class of omega-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter …
Oct. 1, 2008, 2:15 p.m.
Stefan Dziembowski (Rome) (Uniwersytet Warszawski)
How to do cryptography on non-trusted machines?
Most of the real-life attacks on cryptographic devices do not break their mathematical foundations, but exploit vulnerabilities of their implementations. This concerns both the cryptographic software executed on PCs (that can be attacked by viruses), …
June 20, 2008, 2:15 p.m.
Szczepan Hummel (Uniwersytet Warszawski)
On Borel Inseparability of Game Tree Languages
June 4, 2008, 2:15 p.m.
Aymeric Vincent (Uniwersytet Warszawski)
Thomas Colcombet's deterministic version of Simon's decomposition theorem
In this presentation, we will introduce Simon's decomposition theorem and give an outline of the proof given by Thomas Colcombet. We will then concentrate on a weaker version of the theorem which has the advantage …
May 28, 2008, 2:15 p.m.
Jan Chomicki (Buffalo) (Uniwersytet Warszawski)
New Directions in Preference Research
I will survey several recently proposed applications and extensions of a logical approach to preference specification and querying. In that approach, preferences are defined as binary relations that are finitely representable using first-order formulas. Preference …
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 …