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

  • 2019-11-06, godz. 14:15, 5050

    Szymon Toruńczyk (Uniwersytet Warszawski)

    Aggregation, Enumeration, and Updates on Sparse Databases via Circuits

    We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framework allows to treat those problems in a unified way, by considering various semirings, depending on the considered probl...

  • 2019-10-30, godz. 14:15, 5050

    Michał Pilipczuk (Uniwersytet Warszawski)

    n^n is not poly-recursive

    A sequence (a_n)_{n\geq 0} is poly-recursive if there is a finite set of sequences, one of them being (a_n)_{n\geq 0}, which can be defined using a system of recursive equations of the following form: the nth entry of each sequence is equal to a polynomial of the (n-1)st entries of all the seque...

  • 2019-10-23, godz. 14:15, 5050

    Paweł Parys (Uniwersytet Warszawski)

    Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time

    Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they ope...

  • 2019-10-16, godz. 14:15, 5050

    Nathan Lhote (joint with Mikołaj Bojańczyk and Sandra Kiefer) (Uniwersytet Warszawski)

    String-to-String Interpretations with Polynomial-Size Output

    String-to-string mso-interpretations are like Courcelle’s mso-transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to mso...

  • 2019-10-09, godz. 14:15, 5050

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    On Boolean closed full trios for ω-words (joint work with Edon Kelmendi, Rafał Stefański and Georg Zetzsche)

    Zetzsche and Lohrey showed that if a class of languages of finite words: 1. is closed under Boolean combinations; and 2. is closed under images of rational transductions (=NFA’s with output); 3. contains at least one non-regular language   then the class contains the entire arithmetic...

  • 2019-06-26, godz. 14:15, 5050

    Stefan Göller (Universität Kassel)

    A lower bound approach for automata involving clocks or counters

    The main part of my talk will be about a more in-depth explanation of a lower bound approach for the emptiness problem for automata involving clocks or counters developed jointly with Markus Lohrey. It combines two known results from complexity theory, namely (1) the leaf language cha...

  • 2019-06-19, godz. 14:15, 5050

    Krzysztof Ziemiański (Uniwersytet Warszawski)

    Higher Dimensional Automata

    Higher Dimensional Automata (HDA), introduced by Pratt and van Glabbeek (1991), are one of models of concurrency, notable for its high expressivity. I will recall the definition of HDA and show how to model ST-structures and Petri nets with HDA. I will define executions of a given HDA and its ass...

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

    Vincent Michielini (Uniwersytet Warszawski)

    Uniformization gives the full strength of regular languages

    Given R a binary relation between words (which we treat as a language over a product alphabet A × B),  a uniformisation of it is a language L ⊆ R that  chooses a single word over B, for each word over A. It is known that MSO, the full class of regular languages, is strong ...

  • 2019-06-05, godz. 14:15, 5050

    Radosław Piórkowski (Uniwersytet Warszawski)

    New pumping technique for 2-dimensional VASS

    I will show that every run of 2-VASS allows some kind of pumping: in some cases just a straightforward adaptation of 1D pumping techniques is enough —such runs we call 'thin'. I will prove that if a run is not thin, it is 'thick' — has some nice geometric properties th...

  • 2019-05-29, godz. 14:15, 5050

    Sylvain Schmitz (CNRS & ENS Paris-Saclay)

    The Parametric Complexity of Lossy Counter Machines

       The reachability problem in lossy counter machines is the best-known    ACKERMANN-complete problem and has been used to establish most of the    ACKERMANN-hardness statements in the literature.  This hides however a    complexity gap when t...