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

22 stycznia 2020 14:15
Pierre Simon (UC Berkeley)
Model theory of order-like and tree-like homogeneous structure
I will discuss results towards a model-theoretic classification of order-like homogeneous structures, including for instance all structures FO-definable in a dense linear order. I will also mention ongoing work towards extending this classification to include …
15 stycznia 2020 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Reachability problem for fixed dimensional VASSes
I will present a few recent results about reachability problem for fixed dimensional VASSes. There results invalidate some previously posed conjectures and show that the problem is harder than previously expected to be.
8 stycznia 2020 14:15
Paweł Parys (Uniwersytet Warszawski)
Bisimulation Finiteness of Pushdown Systems Is Elementary
We show that in case a pushdown system is bisimulation equivalent to a finite system, then there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the …
18 grudnia 2019 14:15
Michał Wrocławski (Uniwersytet Warszawski)
How computability depends on notation?
We study abstract notations for natural numbers, which may differ from standard notations, so that the functions and relations classically uncomputable become computable, and vice versa. This question was raised by a philosopher Stewart Shapiro …
11 grudnia 2019 14:15
Sławomir Lasota (Uniwersytet Warszawski)
Extremal counter programming
The aim is to present a technical core of a recently obtained TOWER lower bound for the reachability problem of Petri nets, model equivalent to vector addition systems with states or to nondeterministic counter machines …
4 grudnia 2019 14:15
Michał Skrzypczak (Uniwersytet Warszawski)
Computing measures of weak-MSO definable sets of trees
Michalewski and Mio posed a fundamental question about the possibility of computing standard measures of regular languages of infinite trees. A positive solution (i.e. an algorithm) would allow us to tackle quantitatively a variety of …
27 listopada 2019 14:15
Janusz Schmude (Uniwersytet Warszawski)
An algebraic approach to equivalence of MSO transductions of graphs of bounded treewidth
We prove MSO-transductions of graphs of bounded treewidth have decidable equivalence modulo fractional isomorphism with real coefficients (not necessarily nonnegative). The main goal of this talk is to present a new approach to equivalence problem …
20 listopada 2019 14:15
Ramanathan S. Thinniyam (Max Planck Institute for Software Systems (MPI-SWS))
Regular Separability and Intersection Emptiness are Independent Problems
The problem of regular separability asks, given two languages $K$ and $L$, whether there exists a regular language $S$ with $K \subseteq S$ and $S \cap L = \emptyset$. This problem becomes interesting when the …
13 listopada 2019 14:15
Grzegorz Fabiański (Uniwersytet Warszawski)
Uniformization of MSO-definable relation on integers
We consider the problem to decide, whether a given MSO-definable relation R of the bi-infinite words (words over integers), there exist a MSO-definable function F (a functional relation between bi-infinite words) which uniformize it (meaning …
6 listopada 2019 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Aggregation, Enumeration, and Updates on Sparse Databases via Circuits
We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framework allows to treat those problems in a unified way, by considering various …
30 października 2019 14:15
Michał Pilipczuk (Uniwersytet Warszawski)
n^n is not poly-recursive
A sequence (a_n)_{n\geq 0} is poly-recursive if there is a finite set of sequences, one of them being (a_n)_{n\geq 0}, which can be defined using a system of recursive equations of the following form: the …
23 października 2019 14:15
Paweł Parys (Uniwersytet Warszawski)
Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out …
16 października 2019 14:15
Nathan Lhote (joint with Mikołaj Bojańczyk and Sandra Kiefer) (Uniwersytet Warszawski)
String-to-String Interpretations with Polynomial-Size Output
String-to-string mso-interpretations are like Courcelle’s mso-transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial …
9 października 2019 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
On Boolean closed full trios for ω-words
Zetzsche and Lohrey showed that if a class of languages of finite words: 1. is closed under Boolean combinations; and 2. is closed under images of rational transductions (=NFA’s with output); 3. contains at least …
26 czerwca 2019 14:15
Stefan Göller (Universität Kassel)
A lower bound approach for automata involving clocks or counters
The main part of my talk will be about a more in-depth explanation of a lower bound approach for the emptiness problem for automata involving clocks or counters developed jointly with Markus Lohrey. It combines …