Cotygodniowe seminarium badawcze
Organizatorzy
- prof. dr hab. Mikołaj Bojańczyk
- prof. dr hab. Damian Niwiński
Informacje
środy, 14:15 , sala: 5440Dziedziny badań
Lista referatów
-
26 stycznia 2022 14:15
Jan Otop (Instytut Informatyki, Uniwersytet Wrocławski)
Active learning automata with syntactic queries
Regular languages can be actively learned with membership and equivalence queries in polynomial time. The learning algorithm, called the L^* algorithm, constructs iteratively the right congruence relation of a given regular language L, and returns …
-
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 …