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

Nov. 18, 2020, 2:15 p.m.
Janusz Schmude (MIM UW)
Polynomial grammars with substitution
Polynomial grammars are grammars whose nonterminals generate tuples of integers (or elements of some ring in general) and productions use polynomial functions. They proved to be useful for proving decidability of equivalence of MSO transductions …
Nov. 4, 2020, 2:15 p.m.
Mikołaj Bojańczyk (MIM UW)
Regular expressions for data words
I will discuss a proposal (one of many others) for regular expressions that use infinite alphabets. The regular expressions describe exactly the languages that can be recognised by nondeterministic orbit-finite automata (equivalently, nondeterministic register automata). …
Oct. 21, 2020, 2:15 p.m.
Szymon Toruńczyk (Uniwersytet Warszawski (MIMUW))
A model-theoretic characterization of bounded twin-width
Twin-width is a graph parameter introduced recently in a series of papers by Bonnet, Geniet, Kim, Thomassé, and Watrigant. Among others, classes of bounded twin-width include all proper minor-closed classes, all classes of bounded tree-width …
Oct. 14, 2020, 2 p.m.
Colin Geniet (ENS Paris-Saclay)
Twin-Width of Graphs
Twin-width is a graph complexity measure based on a notion of width of permutations by Guillemot and Marx [SODA '14]. Twin-width is defined through sequences of d-contractions, which witness that the twin-width is at most …
June 24, 2020, 2:15 p.m.
Pierre Pradic (ENS Lyon)
joint work with Lê Thành Dũng (Implicit automata in λ-calculi)
This work is part of an exploration of the expressiveness of the simply-typed λ-calculus (STLC) and related substructural variants (linear, affine, planar) using Church encodings of datatypes. More specifically, we are interested in the connection …
June 17, 2020, 2:15 p.m.
Jakub Gajarsky (Uniwersytet Warszawski)
Differential games for FO logic
I will introduce differential games for FO logic of graphs, a new variant of Ehrenfeucht-Fraisse games. These games are an attempt to extend currently used locality-based techniques for FO logic in a way which works …
June 10, 2020, 2:15 p.m.
Nathanael Fijalkow (CNRS, LaBRI)
Learning Probabilistic Context-Free Grammar
In this talk I will report on a joint work with Alexander Clark about learning (a subclass of) probabilistic context-free grammars published in the Transactions of the Association for Computational Linguistics. The objective of the …
June 3, 2020, 2:15 p.m.
Julian Salamanca (Uniwersytet Warszawski)
Lattices do not distribute over powerset
I will show that there is no distributive law of the free lattice monad over the powerset monad. The proof presented also works for other classes of lattices such as (bounded) distributive/modular lattices and also …
May 27, 2020, 2:15 p.m.
Joost Winter
From automata theory to coinduction with Haskell
In this talk I will approach a topic from classical automata theory, power series in a single input variable, from the point of view of coinductive specifications in the functional language Haskell, which are easy …
May 20, 2020, 2:15 p.m.
Vincent Michielini (Uniwersytet Warszawski)
joint work with Michał Skrzypczak (Regular choices and uniformisations for countable domains)
Considering the following question: given (in a sense which will be clarified in the talk) a countable totally ordered set D, on which condition(s) does there exist a choice function over D (i.e. a function …
May 13, 2020, 2:15 p.m.
Denis Kuperberg (CNRS, LIP, ENS Lyon)
joint work with Laureline Pinault and Damien Pous (Computational content of circular proof systems)
Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite …
May 6, 2020, 2:15 p.m.
Filip Mazowiecki (MPI SWS)
joint work with Alejandro Grez, Michał Pilipczuk, Gabriele Puppis and Cristian Riveros (The monitoring problem for timed automata)
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a different perspective, that …
April 29, 2020, 2:15 p.m.
Mikołaj Bojańczyk (Uniwersytet Warszawski)
joint work with Rafał Stefański (Single use transducers over infinite alphabets)
Automata for infinite alphabets, despite the undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and …
April 22, 2020, 2:15 p.m.
Wojciech Czerwiński (Uniwersytet Warszawski)
joint work with Diego Figueira and Piotr Hofman (Universality problem for unambiguous Vector Addition Systems with States)
I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning …
April 15, 2020, 2:15 p.m.
Bartek Klin (Uniwersytet Warszawski)
Monadic MSO logic
The correspondence of regular languages and monadic second-order logic relies on the fact that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for finite words, but …