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

Feb. 18, 2009, 2:15 p.m.
Łukasz Kaiser (Aachen)
Basic Analysis of Structure Rewriting Systems
A single state of an analyzed system has, in practice, often a complex structure in itself, while in theory it is usually simple in some sense, e.g. it can be a tree. We show how …
Jan. 21, 2009, 2:15 p.m.
Henryk Michalewski (Uniwersytet Warszawski)
Complete pairs of coanalytic sets
Jan. 10, 2009, 2:15 p.m.
Robert Dąbrowski (Uniwersytet Warszawski)
Introducing equations in free semigroup
Let be given a free monoid with a set of generators E whose cardinality is at least 2. We shall call elements of E 'letters' and elements of E* 'words'. Let also be given a …
Jan. 6, 2009, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
A geometrical approach to star height
I will talk about an algorithm deciding limitedness of distance desert automata (which is the hard part in deciding star height). The algorithm itself is quite simple, and the correctness argument involves concepts such as …
Dec. 10, 2008, 2:15 p.m.
Tomasz Idziaszek (Uniwersytet Warszawski)
EF logic
I will talk about a simple temporal logic EF over finite words, infinite words and finite trees. I will show that a language is definable by an EF formula if and only if its syntactic …
Dec. 3, 2008, 2:15 p.m.
Leszek Kołodziejczyk (Uniwersytet Warszawski)
Parity games in weak arithmetic theories
Parity games in weak arithmetic theories I will present A. Beckmann and F. Moller's paper "On the complexity of parity games". The main result of the paper is that positional determinacy of parity games can …
Nov. 26, 2008, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
The star-height problem
Nov. 5, 2008, 2:15 p.m.
Tomasz Jurdziński (Wrocław)
Leftist grammars
Leftist grammars were introduced as a tool to show decidability of the accessibility problem in certain general protection systems. In the presentation, I will concentrate on complexity of the membership problem for these grammars and …
Oct. 22, 2008, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Max-regular languages (cont.)
Oct. 17, 2008, 2:15 p.m.
Thomas Wilke (Kiel)
and other Modal) Logics in Information Securit (Contract Signing Protocols: A Playground for Temporal)
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 …