Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium „Teoria automatów”

Cotygodniowe seminarium badawcze

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