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

19 czerwca 2019 14:15
Krzysztof Ziemiański (Uniwersytet Warszawski)
Higher Dimensional Automata
Higher Dimensional Automata (HDA), introduced by Pratt and van Glabbeek (1991), are one of models of concurrency, notable for its high expressivity. I will recall the definition of HDA and show how to model ST-structures …
12 czerwca 2019 14:15
Vincent Michielini (Uniwersytet Warszawski)
Uniformization gives the full strength of regular languages
Given R a binary relation between words (which we treat as a language over a product alphabet A × B), a uniformisation of it is a language L ⊆ R that chooses a single word …
5 czerwca 2019 14:15
Radosław Piórkowski (Uniwersytet Warszawski)
New pumping technique for 2-dimensional VASS
I will show that every run of 2-VASS allows some kind of pumping: in some cases just a straightforward adaptation of 1D pumping techniques is enough —such runs we call 'thin'. I will prove that …
29 maja 2019 14:15
Sylvain Schmitz (CNRS & ENS Paris-Saclay)
The Parametric Complexity of Lossy Counter Machines
The reachability problem in lossy counter machines is the best-known ACKERMANN-complete problem and has been used to establish most of the ACKERMANN-hardness statements in the literature. This hides however a complexity …
22 maja 2019 14:15
Karin Quaas (Universität Leipzig)
The Containment Problem for Unambiguous Register Automata
We investigate the complexity of the containment problem: given a register automaton A and an unambiguous register automaton B, is the language accepted by A contained in the language accepted by B? We prove that …
15 maja 2019 14:15
Grzegorz Fabiański (Uniwersytet Warszawski)
Progressive Algorithms for Domination and Independence
I will present an algorithm for the dominating set problem, which has the following features: -- is super-simple (and heuristic-like) -- has a provable polynomial running time on many structural graph classes (and beyond) -- …
8 maja 2019 14:15
Nathan Lhote (Uniwersytet Warszawski)
Computability and continuity of regular functions over ω-words
The class of regular functions from infinite words to infinite words is characterised by MSO-transducers, streaming ω-string transducers (transducers with registers) as well as deterministic two-way transducers with regular look-ahead. In their one-way restriction, the …
24 kwietnia 2019 14:15
Filip Murlak (Uniwersytet Warszawski)
Finite Query Answering in Expressive Description Logics
Evaluating queries in the presence of background knowledge has been extensively studied in several communities. In database theory, it is known as query answering under integrity constraints: given a finite database instance and a set …
17 kwietnia 2019 14:15
Szymon Toruńczyk (Uniwersytet Warszawski)
Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
I will present joint work with Thomas Zeume. In this work, we study a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain …
10 kwietnia 2019 14:15
Alexander Rabinovich (Tel Aviv University)
Degrees of Ambiguity of Büchi Tree Automata
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countable) ambiguous if for every input it has at most finitely (respectively, countable) many accepting …
3 kwietnia 2019 14:15
Nir Piterman (Chalmers University of Technology)
Synthesis From Temporal Specifications
In this talk I will present the GR[1] approach to synthesis, the automatic production of designs from their temporal logic specifications. We are interested in reactive systems, systems that continuously interact with other programs, users, …
27 marca 2019 14:15
Wojciech Czerwiński (Uniwersytet Warszawski)
Towards Regular Separability of Vector Addition Systems
I will present a general approach to regular separability in subclasses of vector addition systems. I will sketch the proofs of two new decidability results for regular separability: 1-VASS languages vs VASS languages and Z-VASS …
20 marca 2019 14:15
Joanna Ochremiak (CNRS, LaBRI, Bordeaux)
On the power of symmetric linear programs
We consider families of symmetric linear programs (LPs) that decide a property of graphs in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer …
13 marca 2019 14:15
Marcin Przybyłko (Uniwersytet Warszawski)
On computing measures of open sets of trees
Since Gogacz et al. proved that regular languages of infinite trees are universally measurable, the problem of computing a measure of a given regular set became an appealing and, it seems, difficult problem. Up …
6 marca 2019 14:15
Mikołaj Bojańczyk (joint work with Szymon Toruńczyk) (Uniwersytet Warszawski)
Fixed dimension polynomial time
We describe a complexity class for sets with atoms, which contains problems on orbit-finite inputs like graph reachability, emptiness and minimisation for automata. The idea is that the algorithm must be polynomial for inputs that …