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

29 kwietnia 2020 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
Single use transducers over infinite alphabets (joint work with Rafał Stefański)
Automata for infinite alphabets, despite the undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and …
22 kwietnia 2020 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Universality problem for unambiguous Vector Addition Systems with States (joint work with Diego Figueira and Piotr Hofman)
I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning …
15 kwietnia 2020 14:15
Bartek Klin (Uniwersytet Warszawski)
Monadic MSO logic
The correspondence of regular languages and monadic second-order logic relies on the fact that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for finite words, but …
8 kwietnia 2020 14:15
David Barozzini (Uniwersytet Warszawski)
Higher-order recursion schemes are an expressive formalism used to define languages of possibly infinite ranked trees.
Higher-order recursion schemes are an expressive formalism used to define languages of possibly infinite ranked trees. We prove, under a syntactical constraint called safety, decidability of the model-checking problem for recursion schemes against properties defined …
1 kwietnia 2020 14:15
Engel Lefaucheux (MPI SWS)
Monniaux Problem in Abstract Interpretation
The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program P, a safety specification φ, and an abstract domain of invariants D, does there exist an inductive …
25 marca 2020 14:15
Radosław Piórkowski (Uniwersytet Warszawski)
(Online seminar) Timed games and deterministic separability)
The presentation is based on my recent joint work with Lorenzo Clemente and Sławomir Lasota. We study a generalisation of Büchi-Landweber games to the timed setting, where Player I plays timed actions and Player II …
18 marca 2020 14:15
-
No seminar
11 marca 2020 14:15
-
No seminar
4 marca 2020 14:15
Gaëtan Douéneau-Tabot (ENS Paris-Saclay)
Optimisation of simple programs using pebble and marble transducers
Several models of automata with outputs (known as transducers) have been defined over the years to describe various classes of “regular-like” functions. Such classes generally have good decidability properties, and they have been shown especially …
26 lutego 2020 14:15
Mikołaj Bojańczyk (Uniwersytet Warszawski)
First-order tree-to-tree functions (joint work with Amina Doumane)
We study tree-to-tree transformations that can be defined in logics such as first-order logic or monadic second-order logic.We show that such transformations can be decomposed into certain primitive transformations, such as tree-to-tree homomorphisms or pre-order traversal, by using combinators such …
5 lutego 2020 14:15
Nathan Lhote (Uniwersytet Warszawski)
Pebble minimization for polyregular functions
We show that a polyregular word-to-word function is regular if and only its output size is at most linear in its input size. Moreover a polyregular function can be realized by: a transducer with …
29 stycznia 2020 14:15
Piotr Hofman (Uniwersytet Warszawski)
Generalized linear equations with unordered data (joint work with Jakub Różycki)
Consider a Petri net in which every token carries a k-element set of data, and whenever we fire a transition then data from consumed and produced tokens are compared for equality and disequality. Such an …
22 stycznia 2020 14:15
Pierre Simon (UC Berkeley)
Model theory of order-like and tree-like homogeneous structure
I will discuss results towards a model-theoretic classification of order-like homogeneous structures, including for instance all structures FO-definable in a dense linear order. I will also mention ongoing work towards extending this classification to include …
15 stycznia 2020 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Reachability problem for fixed dimensional VASSes (joint work with Sławomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki)
I will present a few recent results about reachability problem for fixed dimensional VASSes. There results invalidate some previously posed conjectures and show that the problem is harder than previously expected to be.
8 stycznia 2020 14:15
Paweł Parys (Uniwersytet Warszawski)
Bisimulation Finiteness of Pushdown Systems Is Elementary (joint work with Stefan Göller)
We show that in case a pushdown system is bisimulation equivalent to a finite system, then there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the …