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

Oct. 17, 2018, 2:15 p.m.
Bartosz Klin (Uniwersytet Warszawski)
joint work with Julian Salamanca
Monads are mathematical objects that can be understood as "well-structured ways to collect things". Examples include the monad of finite words, the powerset monad P, the multiset monad, etc. In the talk I will explain …
Oct. 17, 2018, 2:15 p.m.
Jerome Leroux (University of Bordeaux)
CHANGE!) Reachability for Two-Counter Machines with One Test and One Rese
We prove that the reachability relation of two-counter machines with one zero-test and one reset is Presburger-definable and effectively computable. Our proof is based on the introduction of two classes of Presburger-definable relations effectively stable …
Oct. 10, 2018, 2:15 p.m.
Lorenzo Clemente (Uniwersytet Warszawski)
Overview of classical and recent decidability and complexity results for networks of timed communicating automata
We present a journey into the study of timed communicating automata, a rich model of concurrency and communication incorporating timing features. We start from classic results for communicating automata (without time) giving intuitions on the …
Oct. 3, 2018, 2:15 p.m.
Edon Kelmendi (Uniwersytet Warszawski)
joint work with Mikołaj Bojańczyk and Michał Skrzypczak
We consider an extension of monadic second order logic on the infinite binary tree with a probabilistic path quantifier called ∇. Intuitively this quantifier means "the set of branches that satisfy a formula has probability 1". …
June 13, 2018, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Joint work with Michał Pilipczuk
I will show the proof of the result announced in the previous talk. I will also discuss some theoretical applications of this result, in the context of machine learning.
June 6, 2018, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski)
Joint work with Michał Pilipczuk
Classes of bounded expansion, introduced by Nesetril and Ossona de Mendez, are sparse graph classes encompassing classes of planar graphs, classes with bounded maximal degree, classes of bounded treewidth, or more generally, any class of …
May 30, 2018, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
joint work with Wojciech Czerwiński, Laure Daviaud, Nathanael Fijalkow, Marcin Jurdziński, Ranko Lazić
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and universal trees, and register …
May 23, 2018, 2:15 p.m.
Vincent Michielini (Uniwersytet Warszawski)
Uniformization Problem for Variants of First Order Logic over Finite Words
We study the uniformization problem for natural variants of the first order logic over finite words. We show that none of them has the uniformization property, as witnessed by proposed counterexamples.
May 16, 2018, 2:15 p.m.
Samson Abramsky (University of Oxford)
Relating Structure and Power: Comonadic Semantics for Computational Resources
Combinatorial games are widely used in finite model theory, constraint satisfaction, modal logic and concurrency theory to characterize logical equivalences between structures. In particular, Ehrenfeucht-Fraisse games, pebble games, and bisimulation games play a central role. …
May 9, 2018, 2:15 p.m.
Bartosz Klin (Uniwersytet Warszawski)
Mu-calculi with atoms
I will show an extension of modal mu-calculus to sets with atoms, developed jointly with Mateusz Łełyk. Model checking is decidable there, and a correspondence to parity games holds. On the other hand, satisfiability becomes …
April 25, 2018, 2:15 p.m.
Janusz Schmude (Uniwersytet Warszawski)
The “Hilbert Method” for Solving Transducer Equivalence Problems
The "Hilbert Method" applies classical results from algebraic geometry, e.g. Hilbert's Basis Theorem, to prove decidability of equivalence on certain classes of transducers. In the first part, following [1], we will describe the method and …
April 18, 2018, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Piotr Hofman and Georg Zetzsche
There are many natural problems for VASS systems, which are a bit similar in style to the reachability problem, but cannot be directly reduced to reachability. In order to solve them one needs to dig …
April 11, 2018, 2:15 p.m.
Sławomir Lasota (University of Warsaw)
Regular Separability of Well-Structured Transition Systems
We investigate languages recognized by well-structured transition systems (WSTS), i.e., infinite systems with state space ordered by a well quasi-order (WQO). We show that, surprisingly, under very mild assumptions every two disjoint WSTS languages are regularly …
April 4, 2018, 2:15 p.m.
Paweł Parys (Uniwersytet Warszawski)
Recursion Schemes and the WMSO+U Logic
We study the weak MSO logic extended by the unbounding quantifier (WMSO+U), expressing the fact that there exist arbitrarily large finite sets satisfying a given property. We prove that it is decidable whether the tree …
March 28, 2018, 2:15 p.m.
-
thursday plan