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

Oct. 21, 2015, 2:15 p.m.
Colin Riba (École Normale Supérieure de Lyon)
Fibrations of Tree Automata
We propose a notion of morphism between tree automata based on game semantics. These morphisms are winning strategies on a synchronous restriction of the linear implication between acceptance games of automata seen as simple games.Our …
Oct. 14, 2015, 2:15 p.m.
Filip Murlak (Uniwersytet Warszawski)
joint work with Wojciech Czerwinski, Claire David, and Pawel Parys (A decidability result for conjunctive queries over data trees)
I will show how to decide validity and containment for unions ofconjunctive queries in which each conjunctive query uses either dataequalities or data inequalities (but not both). This extendssimultaneously two decidability results by Björklund, Martens, …
Oct. 7, 2015, 2:15 p.m.
Jerzy Marcinkowski (Uniwersytet Wrocławski)
The Hunt for a Red Spider: Conjunctive Query Determinacy Problem is Undecidable
Imagine there is a set {Q_1,...Q_n} of database queries (conjunctivequeries), and, for any database instance D, we have access to theviews Q_1(D),...Q_n(D) defined by these queries.Then they give us another query, Q, and we would …
July 1, 2015, 2:15 p.m.
-
There is no seminar this week
June 24, 2015, 2:15 p.m.
Nathanael Fijalkow (Uniwersytet Warszawski)
The LoCo conjecture
I will talk about the LoCo conjecture, which has been conjecture by Christof Löding and Thomas Colcombet in 2010. It talks about games with counters, and implies the decidability of the Rabin-Mostowski hierarchy.I will show …
June 17, 2015, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
Distributive Laws: an Introduction
In this talk, I will introduce various types of distributive laws as can be found in category. In particular, I will introduce distributive laws between monads, as well as distributive laws between a monad and …
June 3, 2015, 2:15 p.m.
-
There is no seminar this week
May 27, 2015, 2:15 p.m.
Leszek Kołodziejczyk (Uniwersytet Warszawski)
How unprovable is Rabin's theorem?
Second-order arithmetic is an axiomatic theory in a language with two sorts of variables, one for representing natural numbers and the other for representing sets of natural numbers. The theory is roughly as strong as …
May 20, 2015, 2:15 p.m.
Michael Blondin (ENS Cachan and Université de Montréal)
joint work with Alain Finkel, Stefan Göller, Christoph Haase and Pierre McKenzie (Reachability in Two-Dimensional Vector Addition Systems with States)
Known to be decidable since 1981, there still remains a huge gapbetween the best known lower and upper bounds for the reachabilityproblem for vector addition systems with states (VASS). In this talk,the reachability problem is …
May 13, 2015, 2:15 p.m.
Filip Mazowiecki (Uniwersytet Warszawski)
joint work with Cristian Riveros (On the expressibility of copyless cost register automata)
Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed as a new computational model. We study the properties and expressiveness of the copyless CRA. Our studies lead to results that copyless CRA …
May 6, 2015, 2:15 p.m.
-
There is no seminar this week
April 29, 2015, 2:15 p.m.
Adam Witkowski (Uniwersytet Warszawski)
Solving datalog containment via bounded cliquewidth
Containment of monadic datalog over data trees is known to be undecidable in general but decidablefor two fragments: downward programs and linear child-only ones.I will describe a method for deciding the containment by bounding clique-width …
April 22, 2015, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
Coinductive stream calculus
In this talk, I will give an introduction to the coinductive stream calculus (developed by Rutten, McIlroy, and others), its connection to coalgebra, automata theory and implementations in the functional programming language Haskell. We take …
April 15, 2015, 2:15 p.m.
Das Anupam (École Normale Supérieure de Lyon)
A Complete Axiomatization of MSO on Infinite Trees
We show that an adaptation of Peano’s axioms for second-orderarithmetic to the language of MSO completely axiomatizes the theoryover infinite trees. This continues a line of work begun by Büchiand Siefkes with axiomatizations of MSO …
April 8, 2015, 2:15 p.m.
Charles Paperman (Uniwersytet Warszawski)
Regular languages of AC_0
I will present a full proof of the theorem of Barington, Compton, Straubing and Therien characterizing regular languages of AC_0 based on a recent algebraic techniques.