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. 15, 2017, 2:15 p.m.
Ranko Lazic (University of Warwick)
Succinct progress measures for solving parity games
The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasi-polynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm …
Nov. 8, 2017, 2:15 p.m.
Radosław Piórkowski (Uniwersytet Warszawski)
WQO dichotomy conjecture — proof of a special case, part 2
The conjecture claims that there exists a simple criterion for decidability for Petri nets with homogeneous data. We prove a special case of this conjecture for data being 2-edge-coloured graphs. I will outline the overall …
Oct. 25, 2017, 2:15 p.m.
Radosław Piórkowski (Uniwersytet Warszawski)
WQO dichotomy conjecture — proof of a special case
Decidability of many standard decision problems for Petri nets becomes an open problem once we extend the model with data. If we restrict only to homogeneous data domains, according to the WQO Dichotomy Conjecture there …
Oct. 18, 2017, 2:15 p.m.
Nathanael Fijalkow (University College London)
Timed comparisons of semi-Markov processes
A semi-Markov process is like a Markov process, but each transition takes some time to get fired, and this time is determined by a probabilistic distribution over the non-negative reals. In this talk I will …
Oct. 11, 2017, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
mu-calculus with atoms
True to the spirit of "\lambda x. (x with atoms)", I will present a modal mu-calculus with atoms. I will also explain what is wrong with it, and how it could perhaps be improved. This …
Oct. 4, 2017, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Laure Daviaud and Krishna S
We define a class of functions, called first-order list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of …
June 7, 2017, 2:15 p.m.
Sylvain Schmitz (ENS de Cachan)
second part
I'll present an approach to computing downward-closures and solving separability by piecewise-testable sets using ideal decompositions. The talk will be based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
May 31, 2017, 2:15 p.m.
Thomas Zeume (Uniwersytet Warszawski)
Lower bounds in Dynamic Complexity
Unconditional lower bounds are are hard to prove. For this reason recent work on inexpressibility for dynamic complexity has been centered around fragments of DynFO (i.e. the class of queries maintainable using first-order formulas). In …
May 24, 2017, 2:15 p.m.
Sylvain Schmitz (ENS de Cachan)
Downward-closures and PTL separability
I'll present an approach to computing downward-closures and solving separability by piecewise-testable sets using ideal decompositions. The talk will be based on a joint paper with J. Goubault-Larrecq published at ICALP last year.
May 17, 2017, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
Expressiveness of probabilistic modal logics
I will show new proofs of expressiveness of modal logics for probabilistic bisimulation and simulation on continuous-state Labelled Markov Processes, with a new result about Polish spaces on the way. This is joint work with …
May 10, 2017, 2:15 p.m.
Michał Skrzypczak (Uniwersytet Warszawski)
Characterisation of regular tree languages on the second level of Borel hierarchy
I will speak about a new result providing a relatively simple effective characterisation of regular tree languages that belong to the second level of the Borel hierarchy. The result is a next step after a …
April 12, 2017, 2:15 p.m.
Joanna Ochremiak (Universite Paris Diderot)
joint work with Albert Atserias
In this talk I will define a few "popular" proof systems and argue that constraint satisfaction problems which admit small size refutations in those proof systems are exactly the constraint satisfaction problems which can be …
April 5, 2017, 2:15 p.m.
Vincent Penelle (Uniwersytet Warszawski)
MSO + weak U
You all have already been disappointed that MSO+U is undecidable over infinite words. Today, we will show that weakening U to a predicate U_1(X) holding if the distance between two consecutive elements of X is …
March 29, 2017, 2:15 p.m.
Sebastian Siebertz (Uniwersytet Warszawski)
Distributed Domination on Graph Classes of Bounded Expansion
We provide a new constant factor approximation algorithm for the (connected) distance-r dominating set problem on graph classes of bounded expansion. Classes of bounded expansion include many familiar classes of sparse graphs such as planar …
March 22, 2017, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Sławomir Lasota, Jerome Leroux and Patrick Totzke
Data nets are yet another extension of Petri Nets in which the relations between consumed and produced tokens are very restricted. Unordered/Ordered Data Petri Nets (UDPN) from the theory perspective are natural and easy to …