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

5 maja 2021 14:15
Mikołaj Bojańczyk (MIM UW)
Star-free expressions for graphs, and an appropriate first-order logic
In the study of word languages, first-order 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 …
28 kwietnia 2021 14:15
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 …
21 kwietnia 2021 14:15
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 …
14 kwietnia 2021 14:15
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 …
31 marca 2021 14:15
Nathan Lhote (AIx-Marseille University)
Computability of Data-Word 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 …
31 marca 2021 14:15
Sandra Kiefer (MIM UW)
Decomposing and Identifying Graphs with Weisfeiler and Leman
The Weisfeiler-Leman (WL) procedure is a widely-used approach for graph-isomorphism testing. It works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, decompositions are a fundamental tool in structural graph theory and often exploited …
17 marca 2021 14:15
Mohnish Pattathurajan (MIM UW)
Parikh’s theorem for infinite alphabets
We investigate commutative images (Parikh Images) of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of finite ones. We …
10 marca 2021 14:15
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 …
3 marca 2021 14:15
Szymon Toruńczyk (MIM UW)
Ordered graphs of bounded twin-width
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove that those are exactly the classes which avoid …
24 lutego 2021 14:15
Filip Mazowiecki (Max Planck Institute for Software Systems)
Continuous One-Counter Automata
We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper and lower bound tests against the counter value. Additionally, the counter updates associated with taking …
20 stycznia 2021 14:15
Mikołaj Bojańczyk and Bartek Klin (MIM UW)
Vector spaces of orbit-finite dimension, with applications to weighted and unambiguous register automata
We develop the theory of vector spaces spanned by orbit-finite sets, with the main technical result being finite upper bounds on the lengths of increasing chains of equivariant subspaces. We then apply this theory to …
16 grudnia 2020 14:15
Denis Kuperberg (ENS Lyon)
Positive first-order logic on words.
I will present FO+, a restriction of first-order logic where letters are required to appear positively, and the alphabet is partially ordered (for instance by inclusion order if letters are sets of atoms). Restricting predicates …
9 grudnia 2020 14:15
Paweł Parys (MIM UW)
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation
We consider nested fixed-point expressions like µz.νy.µx.f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. Following a recent development for parity games, we …
2 grudnia 2020 14:15
Bartek Klin (MIM UW)
Nondeterministic and co-nondeterministic implies deterministic, for data languages.
I will explain why, if a data language and its complement are both recognized by non-deterministic register automata (without guessing), then they are both recognized by deterministic ones. The proof relies on the technology of …
25 listopada 2020 14:15
Corentin Barloy (University of Lille)
Bidimensional linear recursive sequences and universality of unambiguous register automata
We study the universality and inclusion problems for register automata over equality data (A, =). We show that the universality and inclusion problems can be solved with 2-EXPTIME complexity when both automata are without guessing …