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

March 15, 2017, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Martin Grohe, and Michał Pilipczuk
We prove that for every positive integer k, there exists an mso1-transduction which inputs a graph of linear cliquewidth at most k and outputs, nondeterministically, some clique decomposition of the graph of width bounded by …
March 8, 2017, 2:15 p.m.
Thomas Zeume (Uniwersytet Warszawski)
Reachability is in DynFO
In the talk I will gently introduce the dynamic descriptive complexity framework by Patnaik and Immerman. In their formalisation, the result of a database query is updated by logical formulas after the insertion or deletion …
March 1, 2017, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Deciding Parity Games in Quasipolynomial Time
It is a long-standing open problem whether parity games can be solved in polynomial time. I will present a recent paper by Calude, Jain, Khoussainov, Li, Stephan. They have shown an algorithm that solves a …
Feb. 22, 2017, 2:15 p.m.
Marcin Przybyłko (Uniwersytet Warszawski)
joint work with Damian Niwiński and Michał Skrzypczak
We consider the problem of computing the measure of a regular language of infinite trees with respect to so called coin-flipping measure. While the problem is unsolved in general, some progress has been made. In …
Feb. 15, 2017, 2:15 p.m.
Bruno Guillon (Uniwersytet Warszawski)
joint work with Mikołaj Bojańczyk, Laure Daviaud and Vincent Penelle
This talk is about transductions, which are binary relations on words. We are interested in various models computing transductions (ie, transducers), namely two-way automata with outputs, streaming string transducers and string-to-string MSO transductions. We observe …
Jan. 25, 2017, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
Regular Separability of One Counter Automata
The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. We show that regular separability problem is undecidable for one counter …
Jan. 18, 2017, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Algorithms on infinite structures
I will talk about how one can evaluate programs over infinite structures, and about some attempts of measuring the computational complexity of such programs. Here are some relevant keywords: sets with atoms, LOIS, while-programs with …
Jan. 11, 2017, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
or: power series in a single variable
In this talk, I will show the decidability of equivalence of algebraic streams (or, equivalentnly, power series in a single variable) over commutative rings that are, in some sense "computable". This result is a partial …
Dec. 14, 2016, 2:15 p.m.
Joost Winter (Uniwersytet Warszawski)
Valence automata as weighted automata
In this talk we will discuss a way in which it is possible to regard valence automata as weighted automata over suitably chosen semirings, together with a "threshold language" interpretation. This way, it is possible …
Dec. 7, 2016, 2:15 p.m.
Sebastian Siebertz (Uniwersytet Warszawski)
On neighbourhood complexity and kernels for distance-r dominating sets on nowhere dense classes of graphs
The r-neighbourhood complexity of a vertex set A from a graph G is the number of subsets of A which are induced as r-neighbourhoods of vertices of G. We prove that every sufficiently large set …
Nov. 30, 2016, 2:15 p.m.
Sławomir Lasota (Uniwersytet Warszawski)
WQO Dichotomy Conjecture
I will neither state nor prove any interesting theorem. Instead, I'll formulate an interesting (I hope) conjecture about applicability of well quasi orders (WQO) in decision problems for infinite state systems with data (like Petri …
Nov. 16, 2016, 2:15 p.m.
Petr Jancar (Technical University of Ostrava)
Deciding bisimulation equivalence and semantic finiteness of first-order grammars
The plan is to briefly recall the ideas of the decidability proof for bisimulation equivalence of first-order grammars; the proof (presented at ICALP'14) is an alternative for Senizergues's proof for equational graphs with finite out-degree …
Nov. 9, 2016, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Lorenzo Clemente, Sławomir Lasota and Charles Paperman
Given two families of sets F and G, the separability problem of sets from a class G by sets from a class F asks whether for two given sets U, V in G there exists …
Nov. 2, 2016, 2:15 p.m.
Vincent Penelle (Uniwersytet Warszawski)
Rewriting Higher-order Stack Trees
In this talk, I will present the model of stack tree rewriting systems, as a common extension of higher-order pushdown automata and ground tree rewriting system. I will define the model of stack trees, the …
Oct. 19, 2016, 2:15 p.m.
A V Sreejith (Uniwersytet Warszawski)
Monadic second order logic over countable linear orderings
We will look at words over countable linear orderings (for example, omega words, words over rationals etc). We will then look at languages over such words definable by MSO[<]. Is satisfiability of MSO decidable? Is …