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

Nov. 18, 2009, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Algorithm computing Simon decomposition in polynomial time
Simon decomposition is a very important tool in the finite monoid theory. I will present a new, efficient construction of the Simon decomposition. All previous constructions were starting from a finite monoid. When we have …
Nov. 4, 2009, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Shunichi Amano and Leonid Libkin
Relational schema mappings have been extensively studied in connection with data integration and exchange problems, but mappings between XML schemas have not received the same amount of attention. I will present an attempt to develop …
Oct. 28, 2009, 2:15 p.m.
Diego Figueira (Laboratoire Spécification et Vérification (LSV))
Huge lower bounds of weak logics for data words
I will show how to code very hard problems into the satisfiability of the linear temporal logic (LTL) equipped with one register to store and test data values from positions of a data word. I …
Oct. 21, 2009, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski) (Uniwersytet Warszawski)
Languages over Commutative Alphabets (part 2)
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but …
Oct. 14, 2009, 2:15 p.m.
Eryk Kopczyński (Uniwersytet Warszawski)
Languages over Commutative Alphabets
We consider languages accepted by non-deterministic finite automata and context-free grammars, except that we treat the language in a commutative way: we do not care about the order of letters in the accepted word, but …
Oct. 7, 2009, 2:15 p.m.
Wouter Gelade (Hasselt)
Dynamic Complexity of Formal Languages
We will discuss the dynamic complexity of formal languages. As opposed to static complexity theory, which investigates the complexity of problems over fixed structures, dynamic complexity theory concerns the complexity necessary to maintain the answer …
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
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.)