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

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

  • 2021-10-27, godz. 14:15, 5050

    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 scheme is a formalism to represent/generate an infinite tree, e...

  • 2021-10-20, godz. 14:15, 5050

    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 these games are strong enough to capture essential information about graphs from graph classes whic...

  • 2021-10-13, godz. 14:15, 5050

    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 the standpoint of uniformisability / unambiguity. As ...