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

May 17, 2017, 2:15 p.m.
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 …
May 10, 2017, 2:15 p.m.
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 …
April 12, 2017, 2:15 p.m.
Joanna Ochremiak (Universite Paris Diderot)
joint work with Albert Atserias (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 …
April 5, 2017, 2:15 p.m.
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 …
March 29, 2017, 2:15 p.m.
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 …
March 22, 2017, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
joint work with Sławomir Lasota, Jerome Leroux and Patrick Totzke (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 …
March 15, 2017, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Martin Grohe, and Michał Pilipczuk (Definable decompositions for graphs of bounded linear clique width)
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 (Probability of Regular Sets of Trees)
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 (Regular transductions with origin semantics)
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 (Decidability of equivalence of algebraic streams)
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 …