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

Jan. 9, 2019, 2:15 p.m.
Julian Salamanca Tellez (Uniwersytet Warszawski)
Determinization, an algebraic approach
The algebraic approach to recognizability has been proposed since the 1960s and an instance of non-determinism can be formulated by means of direct images of homomorphisms. In this talk, I will present the general problem …
Dec. 19, 2018, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Polyregular functions
I will describe a class of string-to-string transducers, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). Unlike many …
Dec. 12, 2018, 2:15 p.m.
Piotr Hofman (Uniwersytet Warszawski)
Joint work with Utkarsh Gupta, Preey Shah, S. Akshay (Continuous Reachability for Unordered Data Petri Nets)
What is the best way to reduce complexity? The simple answer is "change the problem". Considering the hardness of Petri net reachability people developed a different notion, namely continuous reachability. During the talk, I will …
Dec. 5, 2018, 2:15 p.m.
Alexandre Vigny (Uniwersytet Warszawski)
Query enumeration and nowhere dense classes of graphs
Given a query q and a relational structure D the enumeration of q over D consists in computing, one element at a time, the set q(D) of all solutions to q on D. The delay …
Nov. 28, 2018, 2:15 p.m.
Ian Pratt-Hartmann (University of Manchester)
The Return of the Syllogism
The Aristotelian syllogistic is known to do a good job of accounting for the validity of inferences couched in a certain common fragment of many natural languages. To take an example from English: Every man …
Nov. 14, 2018, 2:15 p.m.
Laurent Doyen (CNRS & LSV, ENS Paris-Saclay)
Graph Planning with Expected Finite Horizon
A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon …
Nov. 7, 2018, 2:15 p.m.
Bartosz Klin (Uniwersytet Warszawski)
joint work with Julian Salamanca (PP is not a monad)
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. 31, 2018, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
The Reachability Problem for Vector Addition Systems is Not Elementary
I will present a recent result about tower lower bound for reachability problem in VASes. I plan to first illustrate a few phenomena occuring in VASes by examples. Then I will show a full proof …
Oct. 24, 2018, 2:15 p.m.
Nathan Lhote (Uniwersytet Warszawski)
Logics for Transductions
Logics over words such as Monadic Second-Order Logic, or Linear Temporal Logic provide a way to specify properties of systems in a high-level formalism, close to natural language. From such formulas one would like to …
Oct. 17, 2018, 2:15 p.m.
Bartosz Klin (Uniwersytet Warszawski)
joint work with Julian Salamanca (PP is not a monad)
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 (MSO+∇ is undecidable)
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 (Dynamic Enumeration for First-Order Queries on Classes of Bounded Expansion)
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 (Dynamic Enumeration for First-Order Queries on Classes of Bounded Expansion)
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 …