Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

15 listopada 2017 14:15
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 …
8 listopada 2017 14:15
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 …
25 października 2017 14:15
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 …
18 października 2017 14:15
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 …
11 października 2017 14:15
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 …
4 października 2017 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
First-order list functions
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 …
7 czerwca 2017 14:15
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.
31 maja 2017 14:15
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 …
24 maja 2017 14:15
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.
17 maja 2017 14:15
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 …
10 maja 2017 14:15
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 …
12 kwietnia 2017 14:15
Joanna Ochremiak (Universite Paris Diderot)
Proof complexity of constraint satisfaction problems
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 …
5 kwietnia 2017 14:15
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 …
29 marca 2017 14:15
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 …
22 marca 2017 14:15
Piotr Hofman (Uniwersytet Warszawski)
State equation for Data Petri Nets
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 …