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

  • 2019-05-22, godz. 14:15, 5050

    Karin Quaas (Universität Leipzig)

    The Containment Problem for Unambiguous Register Automata

    We investigate the complexity of the containment problem: given a register automaton A and an unambiguous register automaton B, is the language accepted by A contained in the language accepted by B? We prove that the problem is decidable and give upper bounds on the computational complexi...

  • 2019-05-15, godz. 14:15, 5050

    Grzegorz Fabiański (Uniwersytet Warszawski)

    Progressive Algorithms for Domination and Independence

    I will present an algorithm for the dominating set problem, which  has the following features: -- is super-simple (and heuristic-like) -- has a provable polynomial running time on many structural graph  classes (and beyond) -- is not specific to any particular class of graphs and do...

  • 2019-05-08, godz. 14:15, 5050

    Nathan Lhote (Uniwersytet Warszawski)

    Computability and continuity of regular functions over ω-words

    The class of regular functions from infinite words to infinite words is characterised by MSO-transducers, streaming ω-string transducers (transducers with registers) as well as deterministic two-way transducers with regular look-ahead. In their one-way restriction, the latter transduce...

  • 2019-04-24, godz. 14:15, 5050

    Filip Murlak (Uniwersytet Warszawski)

    Finite Query Answering in Expressive Description Logics

    Evaluating queries in the presence of background knowledge has been extensively studied in several communities. In database theory, it is known as query answering under integrity constraints: given a finite database instance and a set of constraints, determine answers to a query that are certain...

  • 2019-04-17, godz. 14:15, 5050

    Szymon Toruńczyk (Uniwersytet Warszawski)

    Register Automata with Extrema Constraints, and an Application to Two-Variable Logic

    I will present joint work with Thomas Zeume. In this work, we study a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of registe...

  • 2019-04-10, godz. 14:15, 5050

    Alexander Rabinovich (Tel Aviv University)

    Degrees of Ambiguity of Büchi Tree Automata

    An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countable) ambiguous if for every input it has at most finitely (respectively, countable) many accepting computations. An automaton is bounded ambiguous if there is k such...

  • 2019-04-03, godz. 14:15, 5050

    Nir Piterman (Chalmers University of Technology)

    Synthesis From Temporal Specifications

    In this talk I will present the GR[1] approach to synthesis, the automatic production of designs from their temporal logic specifications. We are interested in reactive systems, systems that continuously interact with other programs, users, or their environment and specifications in linear tempora...

  • 2019-03-27, godz. 14:15, 5050

    Wojciech Czerwiński (Uniwersytet Warszawski)

    Towards Regular Separability of Vector Addition Systems (joint work with Georg Zetzsche)

    I will present a general approach to regular separability in subclasses of vector addition systems. I will sketch the proofs of two new decidability results for regular separability: 1-VASS languages vs VASS languages and Z-VASS languages and VASS languages. Regular separability of genera...

  • 2019-03-20, godz. 14:15, 5050

    Joanna Ochremiak (CNRS, LaBRI, Bordeaux)

    On the power of symmetric linear programs

    We consider families of symmetric linear programs (LPs) that decide a property of graphs in the sense that,  for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without...

  • 2019-03-13, godz. 14:15, 5050

    Marcin Przybyłko (Uniwersytet Warszawski)

    On computing measures of open sets of trees

    Since Gogacz et al. proved that regular languages of infinite trees are universally measurable,  the problem of computing a measure of a given regular set became an appealing and, it seems, difficult problem.   Up to now, only ``simple'' cases were solved: either...