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

  • 2021-05-19, godz. 14:15, online

    Jan Dreier (TU Wien, Austria)

    Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes

    The concept of bounded expansion provides a robust way to capture sparse graph classes with interesting algorithmic properties. Most notably, every problem definable in first-order logic can be solved in linear time on bounded expansion graph classes. First-order interpretations and transductions of...

  • 2021-05-12, godz. 14:15, online

    Wojciech Czerwiński (MIM UW)

    Reachability in Vector Addition Systems is Ackermann-complete

    Complexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problem for a few decades. Very recently two proofs of Ackermann-hardness were obtained independently (one by Jerome Leroux, one by us). I will present you the proof obtained in a joint work with Łukasz...

  • 2021-05-05, godz. 14:15, online

    Mikołaj Bojańczyk (MIM UW)

    Star-free expressions for graphs, and an appropriate first-order logic

    In the study of word languages, first-order logic is more frequently used with the order predicate x > y, and not the successor predicate x=y+1. (For MSO, there is no difference.) For example, the celebrated equivalence of star-free regular languages with first-order logic uses the first-order logic...

  • 2021-04-28, godz. 14:15, online

    Nathanaël Fijalkow (LaBRI)

    The theory of universal graphs for infinite duration games

    2017 was a special year in the world of parity games. Now that the dust has settled, what have we learned from the new quasi polynomial algorithms? In this talk I'll introduce the notion of universal graphs, and argue the following: - they give nice generic (value iteration) algorithms for any ...

  • 2021-04-21, godz. 14:15, online

    Lorenzo Clemente & Michał Skrzypczak (MIM UW & MIM UW)

    Deterministic and game separability of tree languages via games

    We show that it is decidable whether two regular languages of infinite trees are separable by a deterministic language, resp., a game language. We consider two variants of separability, depending on whether the set of priorities of the separator is fixed, or not. In each case, we show that separabil...

  • 2021-04-14, godz. 14:15, online

    Jakub Różycki (MIM UW)

    On the expressiveness of Büchi arithmetic

    Büchi arithmetic is a logical theory that is important for us, because it is equivalent to regular languages. We show that the existential fragment of Büchi arithmetic is strictly less expressive than full Büchi arithmetic of any base, and moreover establish that its ∃*∀*-fragment is already ...

  • 2021-03-31, godz. 14:15, online

    Sandra Kiefer (MIM UW)

    Decomposing and Identifying Graphs with Weisfeiler and Leman

    The Weisfeiler-Leman (WL) procedure is a widely-used approach for graph-isomorphism testing. It works by iteratively computing an isomorphism-invariant coloring of vertex tuples. Meanwhile, decompositions are a fundamental tool in structural graph theory and often exploited in approaches to tackle t...

  • 2021-03-31, godz. 14:15, online

    Nathan Lhote (AIx-Marseille University)

    Computability of Data-Word Transductions over Atoms

    We investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data ω-words). The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic...

  • 2021-03-17, godz. 14:15, online

    Mohnish Pattathurajan (MIM UW)

    Parikh’s theorem for infinite alphabets

    We investigate commutative images (Parikh Images) of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of finite ones. We prove the following. 1. Parikh Images of one-register...

  • 2021-03-10, godz. 14:15, online

    Pierre Ohlmann (IRIF, Université de Paris)

    Controlling a random population

    Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is dec...