Cotygodniowe seminarium badawcze
2022-01-19, godz. 14:15, 5050
Ł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 of questions about VASSes remain to be solved. Even the reachabi...
2022-01-12, godz. 14:15, 5050
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 a universal graph which is monotone and well-founded. Here, "positional" refers only to th...
2021-12-22, godz. 14:15, online
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 true, then certain other facts must be true as well. In Ontology-Med...
2021-12-15, godz. 14:15, online
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 to infinity and zero, respectively. ...
2021-12-08, godz. 14:15, Online
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 a brief description of atoms and orbit-finite sets. Then I will define vector spaces over orb...
2021-12-01, godz. 14:15, online
Ismaël Jecker (MIM UW)
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 of the Ai. Otherwise, A is prime. This notion of primality was introduced by Orna Kupferman and Jonathan Mosheiff in 2015, but...
2021-11-24, godz. 14:15, online
Krzysztof Ziemiański (MIM UW)
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 subsumption. Then I will define regular interval pomset languages and...
2021-11-17, godz. 14:15, 5050
Jędrzej Kołodziejski (MIM UW)
Taming (un)boundedness - logic, automata and games with countdown
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 and automata define the same...
2021-11-10, godz. 14:15, 5050
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 interplay of this order with notions such as treewidth, clique-width, twin-width, bounded expansion, ...
2021-11-03, godz. 14:15, 5050
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 future-determinization. ...