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

Nov. 27, 2019, 2:15 p.m.
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 …
Nov. 20, 2019, 2:15 p.m.
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 …
Nov. 13, 2019, 2:15 p.m.
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 …
Nov. 6, 2019, 2:15 p.m.
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 …
Oct. 30, 2019, 2:15 p.m.
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 …
Oct. 23, 2019, 2:15 p.m.
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 …
Oct. 16, 2019, 2:15 p.m.
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 …
Oct. 9, 2019, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Edon Kelmendi, Rafał Stefański and Georg Zetzsche (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 …
June 26, 2019, 2:15 p.m.
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 …
June 19, 2019, 2:15 p.m.
Krzysztof Ziemiański (Uniwersytet Warszawski)
Higher Dimensional Automata
Higher Dimensional Automata (HDA), introduced by Pratt and van Glabbeek (1991), are one of models of concurrency, notable for its high expressivity. I will recall the definition of HDA and show how to model ST-structures …
June 12, 2019, 2:15 p.m.
Vincent Michielini (Uniwersytet Warszawski)
Uniformization gives the full strength of regular languages
Given R a binary relation between words (which we treat as a language over a product alphabet A × B), a uniformisation of it is a language L ⊆ R that chooses a single word …
June 5, 2019, 2:15 p.m.
Radosław Piórkowski (Uniwersytet Warszawski)
New pumping technique for 2-dimensional VASS
I will show that every run of 2-VASS allows some kind of pumping: in some cases just a straightforward adaptation of 1D pumping techniques is enough —such runs we call 'thin'. I will prove that …
May 29, 2019, 2:15 p.m.
Sylvain Schmitz (CNRS & ENS Paris-Saclay)
The Parametric Complexity of Lossy Counter Machines
The reachability problem in lossy counter machines is the best-known ACKERMANN-complete problem and has been used to establish most of the ACKERMANN-hardness statements in the literature. This hides however a complexity …
May 22, 2019, 2:15 p.m.
Karin Quaas (Universität Leipzig)
The Containment Problem for Unambiguous Register Automata
We investigate the complexity of the containment problem: given a register automaton A and an unambiguous register automaton B, is the language accepted by A contained in the language accepted by B? We prove that …
May 15, 2019, 2:15 p.m.
Grzegorz Fabiański (Uniwersytet Warszawski)
Progressive Algorithms for Domination and Independence
I will present an algorithm for the dominating set problem, which has the following features: -- is super-simple (and heuristic-like) -- has a provable polynomial running time on many structural graph classes (and beyond) -- …