Organizatorzy

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

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

13 grudnia 2017 14:15
Adrien Boiret (Uniwersytet Warszawski)
Equivalence of Deterministic Top-Down Tree Transducers is ExpTime-Complete
The class of Deterministic Top-Down Tree Transducers (DTOP) has been studied for a long time, but while its equivalence problem was known to be ExpTime-Hard, the best known algorithms were coNExpTime (search of counter-example) or …
6 grudnia 2017 14:15
Juliusz Straszyński (Uniwersytet Warszawski)
PSPACE-complexity of reachability and coverability problems for acyclic Grammar VASes
I will show a reduction of reachablity problem for Grammar VASes to a Subset Sum Game, which is PSPACE-complete.
29 listopada 2017 14:15
Petr Novotny (IST Austria)
Checking and Classifying Fast Termination in VASS
Vector Addition Systems with States (VASS) consists of a finite state machine equipped with d positive integer-valued counters, where in each transition every counter is incremented, decremented, or left unchanged. In this talk, I will …
22 listopada 2017 14:15
Tomasz Gogacz (Uniwersytet Warszawski)
Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend!
I will present a nice result in Knowledge Representation. It is a proof of decidability of query entailment for a certain extension of modal logic. The procedure consists of two semi-recursive procedures. The first is …
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 (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 …
7 czerwca 2017 14:15
Sylvain Schmitz (ENS de Cachan)
Downward-closures and PTL separability (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.
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 …