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 stycznia 2022 14:15
Łukasz Orlikowski (MIM UW)
Improved Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
Complexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problem for a few decades. Despite settling the computational complexity of the reachability problem in VASSes to be Ackermann-complete a lot …
12 stycznia 2022 14:15
Pierre Ohlmann (MIM UW)
Characterising one-player positionality for infinite duration games on graphs
I will present a new result, asserting that a winning condition (or, more generally, a valuation) which admits a neutral letter is positional over arbitrary arenas if and only if for all cardinals there exists …
22 grudnia 2021 14:15
Marcin Przybyłko (University of Bremen)
Answer Counting and Guarded TGDs
Answer Counting is simply the problem of counting the number of solutions to a given query. Tuple-Generating Dependencies (TGDs) are a common formalism for formulating database constraints. A TGD states that if certain facts are …
15 grudnia 2021 14:15
Filip Mazowiecki (Max Planck Institute for Software Systems)
The boundedness and zero isolation problems for weighted automata over nonnegative rationals
We consider linear cost-register automata (equivalently, weighted automata) over the semiring of nonnegative rationals, which generalise probabilistic automata. The two problems boundedness and zero isolation ask whether there is a sequence of words that converge …
8 grudnia 2021 14:15
Arka Ghosh (MIM UW)
Orbit-finite System of Linear Equations (Joint work with P.Hofman and S.Lasota)
An orbit-finite system of linear equations is a system of linear equations where the equations and the variables used in them are possibly infinite but are finite up to certain symmetries. I will start with …
1 grudnia 2021 14:15
Ismaël Jecker (MIM UW)
Composite automata
A finite automaton A is called composite if there exist automata A1, A2, . . . , Ak smaller than A such that the language of A is equal to the intersection of the languages …
24 listopada 2021 14:15
Krzysztof Ziemiański (MIM UW)
Languages of higher dimensional automata and Kleene theorem (joint work with U. Fahrenberg, C. Johansen, G. Struth)
Higher dimensional automata (HDA) are a formalism for modeling concurrent systems introduced by Pratt and van Glabbeek. I will present several ways to define languages of HDA, which are collections of interval pomsets closed under …
17 listopada 2021 14:15
Jędrzej Kołodziejski (MIM UW)
Taming (un)boundedness - logic, automata and games with countdow)
I will present extensions of: the modal fixpoint calculus, parity games, and parity automata - designed to capture (un)boundedness-related phenomena. The extensions lift the classical logic~games~automata correspondence beyond regular properties - in particular the logic …
10 listopada 2021 14:15
Szymon Toruńczyk (MIM UW)
Some results and directions in finite model theory
I will discuss the FO-transduction order on classes of graphs (or other structures), defined by the relation: a class C can be obtained by an FO-transduction from a class D. I will focus on the …
3 listopada 2021 14:15
Piotr Hofman (MIM UW)
Language inclusion for unambiguous VASSes
During the talk, I will present our unpublished results with Wojciech Czerwiński. I will show the decidability of language inclusion for unambiguous VASSes. The main tool is, up to our knowledge, a new concept of …
27 października 2021 14:15
Paweł Parys (MIM UW)
Higher-Order Model Checking Step by Step
I will show a new simple algorithm that solves the model-checking problem for recursion schemes: check whether the tree generated by a given higher-order recursion scheme is accepted by a given alternating parity automaton. Recursion …
20 października 2021 14:15
Jakub Gajarsky (MIM UW)
Differential games, locality, and model checking for FO logic of graphs
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraisse games in which the game is played on one graph only and the moves of both players are restricted. We prove that …
13 października 2021 14:15
Michał Skrzypczak (MIM UW)
Guidable automata and their index problem
Rabin's theorem relies on the equivalence between Monadic Second-Order logic and non-deterministic automata over infinite trees. The non-determinism of the involved model is known to be "inherent", both in terms of descriptive complexity and from …
6 października 2021 14:15
Szymon Toruńczyk (MIM UW)
Model checking separator logic on graphs that exclude a fixed topological minor.
We consider separator logic on graphs introduced recently by Bojańczyk, and independently by Siebertz, Shrader, and Vigny. This logic extends first-order logic by atomic predicates of arity k+2, for each k, expressing that every path …
30 czerwca 2021 14:15
Albert Gutowski (MIM UW)
Finite entailment of non-local queries in description logics
We study the problem of finite entailment of ontology-mediated queries. In particular, we are interested in non-local queries. Recent studies show that a vast majority of user-issued CRPQs only use Kleene star over unions of …