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
-
July 23, 2025, 2:15 p.m.
George Kenison (Liverpool John Moores University)
Decision Problems for P-finite Sequences (Decision Problems for P-finite Sequences)
This talk will discuss the algorithmic analysis of the class of P-finite sequences. These sequences satisfy linear recurrence relations with polynomial coefficients and are common across the quantitative sciences (examples include the Fibonacci, Motzkin, Harmonic, …
-
July 9, 2025, 2:15 p.m.
Omid Yaghoubi (University of Warsaw)
Two-party computation for functions with string inputs (Two-party computation for functions with string inputs)
I will describe a model of computation, which describes functions that input strings, and output elements from some domain, such as the Booleans, or strings, or a field. The idea is that there are two …
-
June 11, 2025, 2:15 p.m.
Arka Ghosh (LaBRI, Université de Bordeaux)
Equivariant ideals and their membership problem (Equivariant ideals and their membership problem)
For an infinite set X (of variables) and a group G acting on X, an ideal J in the polynomial ring K[X] in X over the field K is called equivariant (w.r.t. G) if J …
-
May 21, 2025, 2:15 p.m.
Antonio Casares (University of Warsaw)
A canonical model of automata over infinite words (A canonical model of automata over infinite words)
Contrary to the case of automata over finite words, deterministic parity automaton cannot be minimised in polynomial time, and omega-regular languages do not admit a unique, minimal deterministic automaton. Yet, not all hope is lost! …
-
May 14, 2025, 2:15 p.m.
Wojciech Przybyszewski (University of Warsaw)
Flip-separability (Flip-separability)
Nešetřil and Ossona de Mendez proved that for every nowhere dense graph class C, integer r, and ε > 0 there is some integer k with the following property: For every n-vertex graph G in …
-
April 30, 2025, 2:15 p.m.
Łukasz Kamiński (University of Warsaw)
Reachability in symmetric VASS (Reachability in symmetric VASS)
We investigate the reachability problem in symmetric VASS, where transitions are invariant under a group of permutations of coordinates. One extremal case, the trivial groups, yields general VASS. In another extremal case, the symmetric groups, …
-
April 23, 2025, 2:15 p.m.
Mathieu Lehaut (University of Warsaw)
Asynchronous automata, trees, and reconfigurability (Asynchronous automata, trees, and reconfigurability)
I will present some results about Zielonka's asynchronous automata, which are a popular automata model for concurrent programs. Zielonka's seminal result about distributivity shows that one can go from a centralized specification given by a …
-
April 16, 2025, 2:15 p.m.
Henry Sinclair-Banks (University of Warsaw)
Reaching Semilinear Target Sets in Automata with One Counter (Reaching Semilinear Target Sets in Automata with One Counter)
I will introduce a (novel) generalised reachability problem in automata with one counter with a variety of semantics. The goal of the seminar is to identify what features of target sets make the reachability problem …
-
April 9, 2025, 2:15 p.m.
Aliaume Lopez (University of Warsaw)
Well-quasi-ordered classes of graphs and bounded linear clique-width (Well-quasi-ordered classes of graphs and bounded linear clique-width)
A quasi-ordered set (X, ≤) is a well-quasi-order (WQO) whenever it contains neither infinite antichains, nor infinite decreasing sequences. A cornerstone result of structural graph theory is the Graph Minor Theorem of Robertson and Seymour, …
-
April 2, 2025, 2:15 p.m.
Jakub Gajarský (University of Warsaw)
3D-grids are not transducible from planar graphs (3D-grids are not transducible from planar graphs)
We prove that the class of 3D-grids cannot be obtained by a first-order transduction from the class of planar graphs, and more generally, from any class of graphs of bounded genus. This is a part …
-
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, …
