Organizatorzy

prof. dr hab. Mikołaj Bojańczyk
prof. dr hab. Damian Niwiński

Informacje

środy, 14:15 , sala: 5440

Dziedziny badań

Lista referatów

4 listopada 2026 14:15
Vincent Moreau (Tallinn University of Technology)
A cartesian closed fibration of higher-order regular languages (A cartesian closed fibration of higher-order regular languages)
Higher-order regular language, as introduced by Salvati, form a conservative extension of regular languages of finite words and ranked trees to the simply typed λ-calculus. In this work, we investigate the new closure properties enabled …
28 października 2026 14:15
Nguyễn Lê Thành Dũng (CNRS, LIS, Aix-Marseille Université)
Regularity reflection for higher-order tree transducers and its consequences (Regularity reflection for higher-order tree transducers and its consequences)
First, I will explain why the inverse image of a regular tree language by a higher-order tree transducer — an automaton that computes a tree-to-tree function by manipulating simply typed λ-terms — is itself a …
21 października 2026 14:15
Roland Guttenberg (University of Warsaw)
Determinizing and Unambiguizing Weighted Automata over the Rationals (Determinizing and Unambiguizing Weighted Automata over the Rationals)
In this talk I consider weighted automata (WA) over Q, and am interested in deciding whether there exists an equivalent (1) deterministic and (2) unambiguous WA. In the first half of the talk I state …
14 października 2026 14:15
Colin Geniet (University of Warsaw)
Reducing CMSO to unbreakable graphs cannot be computable (Reducing CMSO to unbreakable graphs cannot be computable)
In groundbreaking work, Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP '18] proved that for any fixed Counting MSO formula φ, testing φ on arbitrary graphs can be reduced to testing φ on highly-connected graphs, in the …
7 października 2026 14:15
Filip Mazowiecki (University of Warsaw)
Stronger bounds on the degree of ambiguity of finite automata (Stronger bounds on the degree of ambiguity of finite automata)
I will discuss some properties and restrictions of nondeterministic finite automata (NFA), for example unambiguous NFA. We have become a bit crazy with my co-authors and I'll write more when the paper appears on arxiv …
24 czerwca 2026 14:15
Paweł Parys (University of Warsaw)
Computing Tarski Fixed Points (Computing Tarski Fixed Points)
This is a not-my-theorem talk. I will present recent results by Xi Chen, Yuhao Li, Mihalis Yannakakis on computing Tarski fixed points in the black-box model. In this problem we consider a monotone function F …
10 czerwca 2026 14:15
Mikołaj Bojańczyk (University of Warsaw)
A machine independent characterisation of the rational string-to-string functions (A machine independent characterisation of the rational string-to-string functions)
This is a not-my-theorem talk. The subject is the rational string-to-string functions, which are those that can be computed by unambiguous automata with output. I will present a Myhill-Nerode style characterisation of these functions, which …
3 czerwca 2026 14:15
Łukasz Kamiński (University of Warsaw)
Integer reachability in data VASS (Integer reachability in data VASS)
Data Vector Addition Systems with States (data VASS) is an extension of plain Vector Addition Systems with States (VASS) for which the decidability status of the reachability problem is still open. We show decidability of …
20 maja 2026 14:15
Clotilde Bizière (University of Warsaw, University of Bordeaux)
Reachability in Branching Vector Addition Systems (BVAS) (Reachability in Branching Vector Addition Systems (BVAS))
The reachability problem for Vector Addition Systems (VAS) admits two fundamentally different decidability proofs. The classical KLM approach relies on a structural decomposition of runs and yields the optimal Ackermannian complexity bounds. A more recent …
13 maja 2026 14:15
Nikolas Mählmann (University of Warsaw)
Hereditary 2-WQO Graph Classes Have Bounded Clique-Width (Hereditary 2-WQO Graph Classes Have Bounded Clique-Width)
A graph class is k-WQO if its k-labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings. We show that every hereditary graph class that is 2-WQO has bounded clique-width. Combined with the recent result of …
29 kwietnia 2026 14:15
Łukasz Orlikowski (University of Warsaw)
Reachability in VASS Extended with Integer Counters (Reachability in VASS Extended with Integer Counters)
I will present our recent result (with Clotilde Bizière, Wojciech Czerwiński, Roland Guttenberg, Jérôme Leroux, Vincent Michielini, Antoni Puch and Henry Sinclair-Banks) about the reachability problem in VASS Extended with Integer Counters (VASS+Z), i.e. an …
22 kwietnia 2026 14:15
Tim Seppelt (IT University of Copenhagen)
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs (Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs)
Lovász (1967) showed that two graphs G and H are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., G and G admit the same number of number of homomorphisms from …
16 kwietnia 2026 13:00
Nagashri Krishnakumar (IIT Madras)
Solving Big Mazes in Small Space - A Monoid Labelling Approach (Solving Big Mazes in Small Space - A Monoid Labelling Approach)
Solving Mazes - more formally, the graph reachability is a fundamental algorithmic problem in space complexity: given a graph and two special vertices s and t, the task is to determine if there is a …
15 kwietnia 2026 14:15
Ninad Rajgopal (Charles University)
Time-space Tradeoffs for Directed s-t Connectivity (Time-space Tradeoffs for Directed s-t Connectivity)
The s-t connectivity problem (STCON), i.e., deciding whether there is a path between two vertices in a directed graph, is a central primitive in graph algorithms and space-bounded complexity. A classical theorem by Savitch shows …
8 kwietnia 2026 14:15
Benedikt Pago (University of Cambridge)
The Finite-Model-Theoretic Complexity of Symmetric Circuits (The Finite-Model-Theoretic Complexity of Symmetric Circuits)
In various areas of complexity theory, there are long-standing open conjectures that are widely believed to be true, but notoriously hard to settle. The obstacle is our apparent inability to prove lower bounds that would …