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

17 października 2008 14:15
Thomas Wilke (Kiel)
Contract Signing Protocols: A Playground for Temporal
8 października 2008 14:15
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 …
1 października 2008 14:15
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), …
20 czerwca 2008 14:15
Szczepan Hummel (Uniwersytet Warszawski)
On Borel Inseparability of Game Tree Languages
4 czerwca 2008 14:15
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 …
28 maja 2008 14:15
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 …
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 …