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

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

    Szymon Toruńczyk (MIM UW)

    Ordered graphs of bounded twin-width

    We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove that those are exactly the classes which avoid certain large grid-like structures as induced substructures...

  • 2021-02-24, godz. 14:15, online

    Filip Mazowiecki (Max Planck Institute for Software Systems)

    Continuous One-Counter Automata

    We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper and lower bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down b...

  • 2021-01-20, godz. 14:15, online

    Mikołaj Bojańczyk and Bartek Klin (MIM UW)

    Vector spaces of orbit-finite dimension, with applications to weighted and unambiguous register automata

    We develop the theory of vector spaces spanned by orbit-finite sets, with the main technical result being finite upper bounds on the lengths of increasing chains of equivariant subspaces. We then apply this theory to weighted register automata, which are a common generalization of weighted automata ...

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