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

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

    Nathan Lhote (Uniwersytet Warszawski)

    Pebble minimization for polyregular functions

    We show that a polyregular word-to-word function is regular if and only  its output size is at most linear in its input size. Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output has quadratic size in its input, a transducer with thre...

  • 2020-01-29, godz. 14:15, 5050

    Piotr Hofman (Uniwersytet Warszawski)

    Generalized linear equations with unordered data (joint work with Jakub Różycki)

    Consider a Petri net in which every token carries a k-element set of data, and whenever we fire a transition then data from consumed and produced tokens are compared for equality and disequality. Such an extension of Petri Nets allows more precise modeling than normal Petri Nets. Of course, comp...

  • 2020-01-22, godz. 14:15, 5050

    Pierre Simon (UC Berkeley)

    Model theory of order-like and tree-like homogeneous structure

    I will discuss results towards a model-theoretic classification of order-like homogeneous structures, including for instance all structures FO-definable in a dense linear order. I will also mention ongoing work towards extending this classification to include structures FO-definable in dense tre...

  • 2020-01-15, godz. 14:15, 5050

    Wojciech Czerwiński (Uniwersytet Warszawski)

    Reachability problem for fixed dimensional VASSes (joint work with Sławomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki)

    I will present a few recent results about reachability problem for fixed dimensional VASSes. There results invalidate some previously posed conjectures and show that the problem is harder than previously expected to be. ...