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-12-16, godz. 14:15, online

    Denis Kuperberg (ENS Lyon)

    Positive first-order logic on words.

    I will present FO+, a restriction of first-order logic where letters are required to appear positively, and the alphabet is partially ordered (for instance by inclusion order if letters are sets of atoms). Restricting predicates to appear positively is for instance very natural when considering logi...

  • 2020-12-09, godz. 14:15, online

    Paweł Parys (MIM UW)

    A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation

    We consider nested fixed-point expressions like µz.νy.µx.f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. Following a recent development for parity games, we show that a quasi-polynomial number of queries is sufficient, namely n^{lg(...

  • 2020-12-02, godz. 14:15, online

    Bartek Klin (MIM UW)

    Nondeterministic and co-nondeterministic implies deterministic, for data languages.

    I will explain why, if a data language and its complement are both recognized by non-deterministic register automata (without guessing), then they are both recognized by deterministic ones. The proof relies on the technology of sets with atoms. This is joint work with Sławek Lasota and Szymon Toru...

  • 2020-11-25, godz. 14:15, online

    Corentin Barloy (University of Lille)

    Bidimensional linear recursive sequences and universality of unambiguous register automata

    We study the universality and inclusion problems for register automata over equality data (A, =). We show that the universality and inclusion problems can be solved with 2-EXPTIME complexity when both automata are without guessing and unambiguous, improving on the currently best-known 2-EXPSPACE upp...

  • 2020-11-18, godz. 14:15, online

    Janusz Schmude (MIM UW)

    Polynomial grammars with substitution

    Polynomial grammars are grammars whose nonterminals generate tuples of integers (or elements of some ring in general) and productions use polynomial functions. They proved to be useful for proving decidability of equivalence of MSO transductions over strings and unordered trees and in general can be...

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

    Mikołaj Bojańczyk (MIM UW)

    Regular expressions for data words

    I will discuss a proposal (one of many others) for regular expressions that use infinite alphabets. The regular expressions describe exactly the languages that can be recognised by nondeterministic orbit-finite automata (equivalently, nondeterministic register automata). The basic idea is to conside...

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