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

  • 2024-02-21, godz. 14:15, 5050

    Vincent Michielini (University of Warsaw)

    Complexity of Maslov's Class K-bar

    Maslov’s class K-bar is a fragment of First-Order Logic consisting of formulae in NNF whose variables occurring in the different atoms obey a certain pattern [*]. It embeds many well-known fragments, such as the two-variable fragment, the Gödel fragment (∀∀∃*), some extensions of modal logi...

  • 2024-02-14, godz. 14:15, 5050

    Daniel Smertnig (University of Ljubljana)

    On the linear hull of a weighted automaton

    Previous work reduces the problem of deciding whether a weighted finite automaton (WFA) over a field is equivalent to a deterministic, respectively, unambiguous, WFA to the computation of the linear hull. The linear hull is the topological closure of the reachability set in a linear version of t...

  • 2024-02-07, godz. 14:15, 5050

    Mikołaj Bojańczyk (University of Warsaw)

    On function spaces for orbit-finite sets

    Joint work with Tito Nguyen and Rafał Stefański. Orbit-finite sets are a generalisation of finite sets, and as such support many operations allowed for finite sets, such as pairing, quotienting, or taking subsets. However, they do not support function spaces, i.e. if X and Y are orbit-finite se...

  • 2024-01-31, godz. 14:15, 5050

    Cristian Riveros Jaeger (Pontificia Universidad Católica de Chile (PUC Chile))

    #NFA admits an FPRAS

    #NFA is the following problem over non-deterministic finite automata (NFA) over words: you receive as input an NFA A and a length N (in unary), and you want to count the number of words of length N accepted by A. Counting the number of solution is a basic algorithmic problem for automata theory, and...

  • 2023-12-20, godz. 14:15, 5050

    Julie Parreaux (University of Warsaw)

    Playing stochastically in Weighted Timed Games to Emulate Memory

    Weighted timed games are two-player zero-sum games played in a timed automaton equipped with integer weights. We consider optimal reachability objectives, in which one of the players, that we call Min, wants to reach a target location while minimising the cumulated weight. While knowing if Min h...

  • 2023-12-13, godz. 14:15, 5050

    Lorenzo Clemente (University of Warsaw)

    Zeroness of weighted basic parallel processes and other finitely generated classes of series

    We consider a weighted model of computation generalising weighted finite automata over fields, namely weighted basic parallel processes (WBPP). The underlying unweighted BPP model, popular in process algebra, was introduced by Christensen in his PhD thesis from 1993 and can be seen as the communic...

  • 2023-12-06, godz. 14:15, 5050

    Antonio Casares (University of Warsaw)

    A characterization of half-positionality for omega-regular languages

    In the context of infinite duration games over graphs, a central question is: For which objectives can the existential player always play optimally using positional (memoryless) strategies? In this talk, we characterize omega-regular objectives with this property. Using this characterization, we obt...

  • 2023-11-29, godz. 14:15, 5050

    Ruiwen Dong (Saarland University)

    Decidability problems in infinite semigroups

    This talk is about several algorithmic problems for matrix semigroups. A classic problem in this area is the well-known Semigroup Membership problem: given as input a finite set of square matrices S = {A1, A2, ... Ak} and a matrix A, decide whether there exists a sequence of matrices from S whose pr...

  • 2023-11-22, godz. 14:15, 5050

    Rafał Stefański (University of Warsaw)

    Recognisable transducers over monads and comonads

    In 2015, Bojańczyk introduced a class of recognizable languages over monads, which is a common generalization of regular languages for many different types of objects, including words, infinite words, and trees. In this talk, I am going to extend this definition to transducers. As it turns out, the...

  • 2023-11-08, godz. 14:15, 5050

    Michał Przybyłek (Polish-Japanese Academy of Information Technology)

    Some remarks on Stone-Čech compactification in ZFA

    Working in Zermelo-Fraenkel Set Theory with Atoms over an \omega-categorical \omega-stable structure, we show how some infinite constructions over definable sets can be encoded as finite constructions over Stone-Čech compactification of the sets. In particular, we show that for a definable set X wi...