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-10-21, godz. 14:15, online

    Szymon Toruńczyk (Uniwersytet Warszawski (MIMUW))

    A model-theoretic characterization of bounded twin-width

    Twin-width is a graph parameter introduced recently in a series of papers by Bonnet, Geniet, Kim, Thomassé, and Watrigant. Among others, classes of bounded twin-width include all proper minor-closed classes, all classes of bounded tree-width or rank-width. We give a model-theoretic characterizat...

  • 2020-10-14, godz. 14:00, online

    Colin Geniet (ENS Paris-Saclay)

    Twin-Width of Graphs

    Twin-width is a graph complexity measure based on a notion of width of permutations by Guillemot and Marx [SODA '14]. Twin-width is defined through sequences of d-contractions, which witness that the twin-width is at most d. Notable classes of graphs with bounded twin-width are proper minor-close...

  • 2020-06-24, godz. 14:15, 5050

    Pierre Pradic (ENS Lyon)

    Implicit automata in λ-calculi (joint work with Lê Thành Dũng (a.k.a. Tito) Nguyễn)

    This work is part of an exploration of the expressiveness of the simply-typed λ-calculus (STLC) and related substructural variants (linear, affine, planar) using Church encodings of datatypes. More specifically, we are interested in the connection with automata theory for string trans...

  • 2020-06-17, godz. 14:15, 5050

    Jakub Gajarsky (Uniwersytet Warszawski)

    Differential games for FO logic

    I will introduce differential games for FO logic of graphs, a new variant of Ehrenfeucht-Fraisse games. These games are an attempt to extend currently used locality-based techniques for FO logic in a way which works naturally on non-sparse graphs. The hope is that the underlying idea can lea...

  • 2020-06-10, godz. 14:15, Online seminar

    Nathanael Fijalkow (CNRS, LaBRI)

    Learning Probabilistic Context-Free Grammar

    In this talk I will report on a joint work with Alexander Clark about learning (a subclass of) probabilistic context-free grammars published in the Transactions of the Association for Computational Linguistics. The objective of the talk is to introduce the main tool: matrix factorisation. ...

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

    Julian Salamanca (Uniwersytet Warszawski)

    Lattices do not distribute over powerset

    I will show that there is no distributive law of the free lattice monad over the powerset monad. The proof presented also works for other classes of lattices such as (bounded) distributive/modular lattices and also for some variants of the powerset monad such as the (nonempty) finite powerse...

  • 2020-05-27, godz. 14:15, Online seminar

    Joost Winter

    From automata theory to coinduction with Haskell

    In this talk I will approach a topic from classical automata theory,  power series in a single input variable, from the point of view of coinductive specifications in the functional language Haskell, which are easy to specify and use due to Haskell's feature of lazy evaluation. In t...

  • 2020-05-20, godz. 14:15, Online seminar

    Vincent Michielini (Uniwersytet Warszawski)

    Regular choices and uniformisations for countable domains (joint work with Michał Skrzypczak)

    Considering the following question: given (in a sense which will be  clarified in the talk) a countable totally ordered set D, on which  condition(s) does there exist a choice function over D (i.e. a  function f: P(D) -> D such that for all nonempty X subset of D, f(...

  • 2020-05-13, godz. 14:15, Online seminar

    Denis Kuperberg (CNRS, LIP, ENS Lyon)

    Computational content of circular proof systems (joint work with Laureline Pinault and Damien Pous)

    Cyclic proofs are a class of formal proof systems that allow some kind of circular reasoning. Unlike classical proofs, represented by finite trees with axioms as leaves, cyclic proofs are represented by trees containing infinite branches. The Curry-Howard correspondence allows us to see these cyclic...

  • 2020-05-06, godz. 14:15, Online seminar

    Filip Mazowiecki (MPI SWS)

    The monitoring problem for timed automata (joint work with Alejandro Grez, Michał Pilipczuk, Gabriele Puppis and Cristian Riveros)

    We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a different perspective, that is, we consider a dynamic version of the problem, called monitoring problem, where the autom...