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

Sept. 30, 2009, 2:15 p.m.
Alessandro Facchini (Lozanna)
Max=Muller, up to Wadge equivalence
Recently, Mikolaj Bojanczyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving many of its usual properties. This new class can be seen as a different way of generalizing …
June 17, 2009, 2:15 p.m.
Dariusz Dereniowski (Uniwersytet Warszawski)
On some searching problems and related graph parameters
During this talk we focus on some graph searching problems. There exist several interesting connections between graph searching and graph parameters. As an example one can mention the correspondence between the minimum number of searchers …
May 27, 2009, 2:15 p.m.
Marcin Bilkowski (Uniwersytet Warszawski)
Unambiguous tree languages
I will talk about the class of unambiguous regular languages of trees. For every language in this class there exists an automaton that accepts this language and admits at most one successful run for every …
May 27, 2009, 2 p.m.
Marcin Bilkowski (Uniwersytet Warszawski)
Unambiguous tree languages
I will talk about the class of unambiguous regular languages of trees. For every language in this class there exists an automaton that accepts this language and admits at most one successful run for every …
May 13, 2009, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Deciding emptiness of min-automata
I will present an algorithm which verifies emptiness of min-automata. This problem is equivalent to the problem of limitedness of Distance Automata and the finite section problem for the semiring of matrices over the (+,min) …
May 6, 2009, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Slawomir Lasota (An automaton for XPath)
I will talk about an automaton model for Xpath. The new model can capture many boolean queries of XPath (in particular, all queries of FOXPath). Consequently, emptiness is undecidable. Nevertheless, the automaton seems interesting for …
April 29, 2009, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
XPath evaluation in linear time
We consider a fragment of XPath where attribute values can be tested for equality (FOXPath). We show that for any fixed unary query in this fragment, the set of nodes that satisfy the query can …
April 22, 2009, 2:15 p.m.
Dexter Kozen (Cornell)
On the Coalgebraic Theory of Kleene Algebra with Tests
We develop a coalgebraic theory of Kleene algebra with tests (KAT) along the lines of Rutten (1998) for Kleene algebra and Chen and Pucella (2003) for a limited version of KAT, resolving two open problems …
April 1, 2009, 2:15 p.m.
Wojciech Czerwiński (joint work with Sławomir Lasota) (Uniwersytet Warszawski)
Partially Commutative Context Free Processes (cont.)
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 …