Weekly research seminar
Organizers
 prof. dr hab. Mikołaj Bojańczyk
 prof. dr hab. Damian Niwiński
Information
Wednesdays, 2:15 p.m. , room: 5050Research fields
List of talks

June 16, 2021, 2:15 p.m.
Lê Thành Dũng (Tito) Nguyễn (LIPN (Paris Nord))
Comparisonfree polyregular functions
We introduce a new automatatheoretic class of stringtostring functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a restricted variant of pebble transducers, and a few inductive definitions that close …

June 9, 2021, 2:15 p.m.
Amina Doumane (CNRSENS Lyon)
Regular expressions for languages of graphs of treewidth 2
I propose a syntax of regular expressions which capture exactly CMSO definable languages of graphs of treewidth 2. A similar syntax is given for CMSO definable languages of seriesparallel graphs and of connected treewidth 2 …

June 2, 2021, 2:15 p.m.
Gaëtan Douéneau (IRIF, Université de Paris)
Pebble transducers with unary output
Bojańczyk recently initiated an intensive study of deterministic pebble transducers, which are twoway automata that can drop marks (named "pebbles") on their input word, and produce an output word. They describe functions from words to …

May 26, 2021, 2:15 p.m.
Sandra Kiefer (MIM UW)
Logarithmic WeisfeilerLeman Identifies All Planar Graphs
The WeisfeilerLeman (WL) algorithm is a wellknown combinatorial procedure for detecting symmetries in graphs that is widely used in graphisomorphism tests. It proceeds by iteratively computing vertex colours. The number of iterations needed to obtain …

May 19, 2021, 2:15 p.m.
Jan Dreier (TU Wien, Austria)
Lacon and ShrubDecompositions: A New Characterization of FirstOrder Transductions of Bounded Expansion Classes
The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in firstorder logic can be solved in linear time on bounded expansion …

May 12, 2021, 2:15 p.m.
Wojciech Czerwiński (MIM UW)
Reachability in Vector Addition Systems is Ackermanncomplete
Complexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problem for a few decades. Very recently two proofs of Ackermannhardness were obtained independently (one by Jerome Leroux, one by us). …

May 5, 2021, 2:15 p.m.
Mikołaj Bojańczyk (MIM UW)
Starfree expressions for graphs, and an appropriate firstorder logic
In the study of word languages, firstorder logic is more frequently used with the order predicate x > y, and not the successor predicate x=y+1. (For MSO, there is no difference.) For example, the celebrated …

April 28, 2021, 2:15 p.m.
Nathanaël Fijalkow (LaBRI)
The theory of universal graphs for infinite duration games
2017 was a special year in the world of parity games. Now that the dust has settled, what have we learned from the new quasi polynomial algorithms? In this talk I'll introduce the notion of …

April 21, 2021, 2:15 p.m.
Lorenzo Clemente & Michał Skrzypczak (MIM UW & MIM UW)
Deterministic and game separability of tree languages via games
We show that it is decidable whether two regular languages of infinite trees are separable by a deterministic language, resp., a game language. We consider two variants of separability, depending on whether the set of …

April 14, 2021, 2:15 p.m.
Jakub Różycki (MIM UW)
On the expressiveness of Büchi arithmetic
Büchi arithmetic is a logical theory that is important for us, because it is equivalent to regular languages. We show that the existential fragment of Büchi arithmetic is strictly less expressive than full Büchi arithmetic …

March 31, 2021, 2:15 p.m.
Sandra Kiefer (MIM UW)
Decomposing and Identifying Graphs with Weisfeiler and Leman
The WeisfeilerLeman (WL) procedure is a widelyused approach for graphisomorphism testing. It works by iteratively computing an isomorphisminvariant coloring of vertex tuples. Meanwhile, decompositions are a fundamental tool in structural graph theory and often exploited …

March 31, 2021, 2:15 p.m.
Nathan Lhote (AIxMarseille University)
Computability of DataWord Transductions over Atoms
We investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data ωwords). The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite …

March 17, 2021, 2:15 p.m.
Mohnish Pattathurajan (MIM UW)
Parikh’s theorem for infinite alphabets
We investigate commutative images (Parikh Images) of languages recognised by register automata and grammars. Semilinear and rational sets can be naturally extended to this setting by allowing for orbitfinite unions instead of finite ones. We …

March 10, 2021, 2:15 p.m.
Pierre Ohlmann (IRIF, Université de Paris)
Controlling a random population
Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller …

March 3, 2021, 2:15 p.m.
Szymon Toruńczyk (MIM UW)
Ordered graphs of bounded twinwidth
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twinwidth. In particular, we prove that those are exactly the classes which avoid …