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-02-05, godz. 14:15, 5050

    Nathan Lhote (Uniwersytet Warszawski)

    Pebble minimization for polyregular functions

    We show that a polyregular word-to-word function is regular if and only  its output size is at most linear in its input size. Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output has quadratic size in its input, a transducer with thre...

  • 2020-01-29, godz. 14:15, 5050

    Piotr Hofman (Uniwersytet Warszawski)

    Generalized linear equations with unordered data (joint work with Jakub Różycki)

    Consider a Petri net in which every token carries a k-element set of data, and whenever we fire a transition then data from consumed and produced tokens are compared for equality and disequality. Such an extension of Petri Nets allows more precise modeling than normal Petri Nets. Of course, comp...

  • 2020-01-22, godz. 14:15, 5050

    Pierre Simon (UC Berkeley)

    Model theory of order-like and tree-like homogeneous structure

    I will discuss results towards a model-theoretic classification of order-like homogeneous structures, including for instance all structures FO-definable in a dense linear order. I will also mention ongoing work towards extending this classification to include structures FO-definable in dense tre...

  • 2020-01-15, godz. 14:15, 5050

    Wojciech Czerwiński (Uniwersytet Warszawski)

    Reachability problem for fixed dimensional VASSes (joint work with Sławomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki)

    I will present a few recent results about reachability problem for fixed dimensional VASSes. There results invalidate some previously posed conjectures and show that the problem is harder than previously expected to be. ...

  • 2020-01-08, godz. 14:15, 5050

    Paweł Parys (Uniwersytet Warszawski)

    Bisimulation Finiteness of Pushdown Systems Is Elementary (joint work with Stefan Göller)

    We show that in case a pushdown system is bisimulation equivalent to a finite system, then there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the pushdown system. As a consequence we obtain that it is elementarily decidable if a g...

  • 2019-12-18, godz. 14:15, 5050

    Michał Wrocławski (Uniwersytet Warszawski)

    How computability depends on notation?

    We study abstract notations for natural numbers, which may differ from standard notations, so that the functions and relations classically uncomputable become computable, and vice versa.  This question was raised by a philosopher Stewart Shapiro in course of  the debate on Church-Turin...

  • 2019-12-11, godz. 14:15, 5050

    Sławomir Lasota (Uniwersytet Warszawski)

    Extremal counter programming

    The aim is to present a technical core of a recently obtained TOWER lower bound for the reachability problem of Petri nets, model equivalent to vector addition systems with states or to nondeterministic counter machines without zero tests. Using an equivalent syntax of 'counter programs...

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

    Michał Skrzypczak (Uniwersytet Warszawski)

    Computing measures of weak-MSO definable sets of trees

    Michalewski and Mio posed a fundamental question about the possibility of computing standard measures of regular languages of infinite trees. A positive solution (i.e. an algorithm) would allow us to tackle quantitatively a variety of specification logics, like CTL* etc. Unfortunately, the general p...

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

    Janusz Schmude (Uniwersytet Warszawski)

    An algebraic approach to equivalence of MSO transductions of graphs of bounded treewidth

    We prove MSO-transductions of graphs of bounded treewidth have decidable  equivalence modulo fractional isomorphism with real coefficients (not necessarily nonnegative). The main goal of this talk is to present a new approach to equivalence problem of MSO-transductions of graphs of bounded ...

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

    Ramanathan S. Thinniyam (Max Planck Institute for Software Systems (MPI-SWS))

    Regular Separability and Intersection Emptiness are Independent Problems

    The problem of regular separability asks, given two languages $K$ and $L$, whether there exists a regular language $S$ with $K \subseteq S$ and $S \cap L = \emptyset$. This problem becomes interesting when the input languages $K$ and $L$ are drawn from language classes beyond the regular languages. ...