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-10-06, godz. 14:15, 5050

    Szymon Toruńczyk (MIM UW)

    Model checking separator logic on graphs that exclude a fixed topological minor.

    We consider separator logic on graphs introduced recently by Bojańczyk, and independently by Siebertz, Shrader, and Vigny. This logic extends first-order logic by atomic predicates of arity k+2, for each k, expressing that every path from a vertex s to a vertex t must pass through one of the ver...

  • 2021-06-30, godz. 14:15, online

    Albert Gutowski (MIM UW)

    Finite entailment of non-local queries in description logics

    We study the problem of finite entailment of ontology-mediated queries. In particular, we are interested in non-local queries. Recent studies show that a vast majority of user-issued CRPQs only use Kleene star over unions of roles. We show how to answer such simple CRPQs, mediated by ontologies exp...

  • 2021-06-23, godz. 14:15, online

    Andrzej Murawski (University of Oxford)

    Verifying higher-order concurrency with data automata

    Using a combination of automata-theoretic and game-semantic techniques, we propose a method for analysing higher-order concurrent programs. Our language of choice is Finitary Idealised Concurrent Algol (FICA) due to its relatively simple fully abstract game model. Our first contribution is an aut...

  • 2021-06-16, godz. 14:15, online

    Lê Thành Dũng (Tito) Nguyễn (LIPN (Paris Nord))

    Comparison-free polyregular functions

    We introduce a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a restricted variant of pebble transducers, and a few inductive definitions that close the class of regular functions under certain ...

  • 2021-06-09, godz. 14:15, online

    Amina Doumane (CNRS-ENS Lyon)

    Regular expressions for languages of graphs of tree-width 2

    I propose a syntax of regular expressions which capture exactly CMSO definable languages of graphs of tree-width 2. A similar syntax is given for CMSO definable languages of series-parallel graphs and of connected tree-width 2 graphs....

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

    Gaëtan Douéneau (IRIF, Université de Paris)

    Pebble transducers with unary output

    Bojańczyk recently initiated an intensive study of deterministic pebble transducers, which are two-way automata that can drop marks (named "pebbles") on their input word, and produce an output word. They describe functions from words to words. Two natural restrictions of this definition have been i...

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

    Sandra Kiefer (MIM UW)

    Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

    The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs that is widely used in graph-isomorphism tests. It proceeds by iteratively computing vertex colours. The number of iterations needed to obtain the final output is crucial for the parallelis...

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