You are not logged in |
Weekly research seminar
Organizers
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Information
Wednesdays, 2:15 p.m. , room: 5440Research fields
List of talks
-
March 26, 2025, 2:15 p.m.
Francesco Dolce (Czech Technical University in Prague)
A gentle introduction to bifix codes and dendric languages (A gentle introduction to bifix codes and dendric languages)
A code is a set of words over an alphabet which can be uniquely decoded when concatenated. It is a bifix code if none of its elements is a prefix or a suffix of another …
-
March 19, 2025, 2:15 p.m.
Michał Skrzypczak (University of Warsaw)
Generalised Quantifiers Based on Rabin-Mostowski Index (Generalised Quantifiers Based on Rabin-Mostowski Index)
I will present our novel results obtained with Denis Kuperberg, Damian Niwiński, and Paweł Parys. The framework is Monadic Second-Order (MSO) logic over \omega-words and infinite trees. We begin with the index problem, which asks, …
-
March 12, 2025, 2:15 p.m.
Wojciech Przybyszewski (University of Warsaw)
Flipping and forking (Flipping and forking)
In model theory, a model is called stable if it does not encode arbitrarily long linear orders using a single fixed formula, ensuring a form of combinatorial tameness. Stability is a central concept in Shelah’s …
-
March 5, 2025, 2:15 p.m.
Vincent Michielini (University of Warsaw)
Query Entailment Problem for S (Query Entailment Problem for S)
In description logic, possibly infinite structures are described via an ABox A (i.e. a basic finite structure, to be completed), and an ontology T (or a TBox, a finite set of constraints aiming to complete …
-
Feb. 26, 2025, 2:15 p.m.
Karolina Drabik (University of Warsaw)
Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs (Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs)
Two fundamental classes of finite automata are deterministic and nondeterministic ones (DFAs and NFAs). Natural intermediate classes arise from bounds on an NFA's allowed ambiguity, i.e. number of accepting runs per word: unambiguous, finitely ambiguous, …
-
Feb. 19, 2025, 2:15 p.m.
Rafał Stefański (University of Warsaw)
Polyregular model checking (Polyregular model checking)
We reduce the model checking problem for a subset of Python to the satisfiability of a first-order formula over finite words, which is known to be decidable. The reduction is based on the theory of …
-
Feb. 5, 2025, 2:15 p.m.
Wojciech Czerwiński (University of Warsaw)
Reachability in 3-VASS is Elementary (Reachability in 3-VASS is Elementary)
I will present our recent result (with Ismael Jecker, Sławomir Lasota and Łukasz Orlikowski) about the reachability problem in 3-dimensional Vector Addition Systems with States (VASS). We have shown that the problem is in 2-ExpSpace, …
-
Jan. 29, 2025, 2:15 p.m.
Andrew Ryzhikov (University of Warsaw)
A guide to tax-free travelling between codes, automata and matrices (A guide to tax-free travelling between codes, automata and matrices)
In this tutorial talk, I will describe a tight and fruitful relationship between variable-length codes (bases of free submonoids of a free monoid), unambiguous finite automata and semigroups of zero-one matrices. I will concentrate on …
-
Jan. 22, 2025, 2:15 p.m.
Giannos Stamoulis (University of Warsaw)
Low rank MSO (Low rank MSO)
We introduce a new logic for describing properties of graphs, which is called low rank MSO. This is the fragment of monadic second-order logic (MSO), in which set quantification is restricted to sets of bounded …
-
Jan. 15, 2025, 2:15 p.m.
Mikołaj Bojańczyk (University of Warsaw)
Graphs of unbounded linear cliquewidth. (Graphs of unbounded linear cliquewidth.)
We show that for every class C of graphs, one of the following holds: 1. The class has bounded linear cliquewidth; or 2. There is a surjective MSO transduction from C to the class of …
-
Dec. 18, 2024, 2:15 p.m.
Lorenzo Clemente (University of Warsaw)
The commutativity problem for varieties of formal series and applications (The commutativity problem for varieties of formal series and applications)
Let Σ be a finite alphabet of noncommuting indeterminates. A *formal series* over the rational numbers is a mapping Σ* → ℚ. We say that it is *commutative* if the output does not depend on …
-
Dec. 11, 2024, 2:15 p.m.
Martin Grohe (RWTH Aachen University)
Some Thoughts on Graph Similarity (Some Thoughts on Graph Similarity)
We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss the complexity of computing the distances.
-
Dec. 4, 2024, 2:15 p.m.
Paweł Parys (University of Warsaw)
A Dichotomy Theorem for Ordinal Ranks in MSO (A Dichotomy Theorem for Ordinal Ranks in MSO)
We focus on formulae ∃X.ϕ(Y, X) of monadic second-order logic over the full binary tree, such that the witness X is a well-founded set. The ordinal rank rank(X) < ω_1 of such a set X …
-
Nov. 27, 2024, 2:15 p.m.
Michał Skrzypczak (University of Warsaw)
Index problem for tree automata - revisited (Index problem for tree automata - revisited)
This talk is mostly "other people's work" type of a talk. However, it is meant to prepare ground for the next week, when Paweł Parys will present our joint results with Damian Niwiński. I want …
-
Nov. 20, 2024, 2:15 p.m.
Mikołaj Bojańczyk (University of Warsaw)
Transducers and straight line programs (Transducers and straight line programs)
In this talk, a straight line program (SLP) is a context-free grammar that generates a single string. This can be viewed as a compression scheme, with the compressed string being possibly exponentially smaller than the …
