Organizatorzy

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

Informacje

środy, 14:15 , sala: 5050

Dziedziny badań

Lista referatów

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 …
18 listopada 2020 14:15
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 …
4 listopada 2020 14:15
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). …
21 października 2020 14:15
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 …
14 października 2020 14:00
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 …
24 czerwca 2020 14:15
Pierre Pradic (ENS Lyon)
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 …
17 czerwca 2020 14:15
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 …
10 czerwca 2020 14:15
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 …
3 czerwca 2020 14:15
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 …
27 maja 2020 14:15
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 …