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

  • 2020-04-29, godz. 14:15, Online seminar

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    Single use transducers over infinite alphabets (joint work with Rafał Stefański)

    Automata for infinite alphabets, despite the undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and mso gives yet another...

  • 2020-04-22, godz. 14:15, Online seminar

    Wojciech Czerwiński (Uniwersytet Warszawski)

    Universality problem for unambiguous Vector Addition Systems with States (joint work with Diego Figueira and Piotr Hofman)

    I will show that the universality problem is ExpSpace-complete for unambiguous VASS, which is in strong contrast with Ackermann-completeness of the same problem for nondeterministic VASS. I also plan to present some more results concerning the interplay between unambiguity and VASS. ...

  • 2020-04-15, godz. 14:15, Online seminar

    Bartek Klin (Uniwersytet Warszawski)

    Monadic MSO logic

    The correspondence of regular languages and monadic second-order logic relies on the fact that the class of regular languages is closed under images of surjective letter-to-letter homomorphisms. This closure property holds for finite words, but also for infinite words, finite or infinite trees, and ...

  • 2020-04-08, godz. 14:15, Online seminar

    David Barozzini (Uniwersytet Warszawski)

    Higher-order recursion schemes are an expressive formalism used to define languages of possibly infinite ranked trees.

    Higher-order recursion schemes are an expressive formalism used to define languages of possibly infinite ranked trees. We prove, under a syntactical constraint called safety, decidability of the model-checking problem for recursion schemes against properties defined by alternating B-automata, an ex...

  • 2020-04-01, godz. 14:15, Online seminar

    Engel Lefaucheux (MPI SWS)

    Monniaux Problem in Abstract Interpretation

    The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: given a program P, a safety specification φ, and an abstract domain of invariants D, does there exist an inductive invariant I in D guaranteeing that program P meets its s...

  • 2020-03-25, godz. 14:15, Online seminar

    Radosław Piórkowski (Uniwersytet Warszawski)

    (Online seminar) Timed games and deterministic separability

    The presentation is based on my recent joint work with Lorenzo Clemente and Sławomir Lasota. We study a generalisation of Büchi-Landweber games to the timed setting, where Player I plays timed actions and Player II replies immediately with untimed actions. The winning condition is ...

  • 2020-03-18, godz. 14:15, 5050

    No seminar

  • 2020-03-11, godz. 14:15, 5050

    No seminar

  • 2020-03-04, godz. 14:15, 5050

    Gaëtan Douéneau-Tabot (ENS Paris-Saclay)

    Optimisation of simple programs using pebble and marble transducers

    Several models of automata with outputs (known as transducers) have been defined over the years to describe various classes of “regular-like” functions. Such classes generally have good decidability properties, and they have been shown especially relevant for program verification o...

  • 2020-02-26, godz. 14:15, 5050

    Mikołaj Bojańczyk (Uniwersytet Warszawski)

    First-order tree-to-tree functions (joint work with Amina Doumane)

    We study tree-to-tree transformations that can be defined in logics such as first-order logic or monadic second-order logic.We show that such transformations can be decomposed into certain primitive transformations, such as tree-to-tree homomorphisms or pre-order traversal, ...