Lista referatów

• 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)

  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 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)

  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 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. ...

Strony