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

March 25, 2009, 2:15 p.m.
Paweł Parys (joint work with Igor Walukiewicz) (Uniwersytet Warszawski)
Weak Alternating Timed Automata
Alternating timed automata on infinite words are considered. The main result is the characterization of acceptance conditions for which the emptiness problem for the automata is decidable. This result implies new decidability results for fragments …
March 25, 2009, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Lower bound for computing fixed points
We consider the following problem: There is given a monotone K-argument function f defined on N-bit sequences {0,1}^N. There is also given the following simpliest possible mu-calculus expression: mi(x1).ni(x2).mi(x3).ni(x4)...mi(xK).f(x1,...,xK). The function is given as a …
March 18, 2009, 2:15 p.m.
Wojciech Czerwiński (joint work with Sławomir Lasota) (Uniwersytet Warszawski)
Partially Commutative Context Free Processes
I will talk about some new class of processes (transition systems) which could be useful for investigating properties of the Process Algebra (PA), a well known class of transition systems. In particular I will show …
March 11, 2009, 2:15 p.m.
Mikołaj Bojańczyk (joint work with Tomasz Idziaszek and Wojciech Czerwiński) (Uniwersytet Warszawski)
Forest algebra for infinite forests
I will talk about an extension of forest algebra for ω-forests. We show how the standard algebraic notions (free object, syntactic algebra, morphisms, etc) extend to the inﬁnite case. To prove its usefulness, I will …
March 4, 2009, 2:15 p.m.
Szymon Toruńczyk (joint work with Mikołaj Bojańczyk) (Uniwersytet Warszawski)
Min-regular languages
A new class of languages of inﬁnite words is introduced, called the min-regular languages, extending the class of omega-regular languages. Min-regular languages are somehow dual to max-regular languages introduced before. The class has two equivalent …
Feb. 25, 2009, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Lower bound for computing fixed points
We consider the following problem: There is given a monotone K-argument function f defined on N-bit sequences {0,1}^N. There is also given the following simpliest possible mu-calculus expression: mi(x1).ni(x2).mi(x3).ni(x4)...mi(xK).f(x1,...,xK). The function is given as a …
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.)