You are not logged in | log in

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminar Automata Theory

Weekly research seminar

List of talks

  • 2023-12-06, 14:15, 5050

    Antonio Casares (University of Warsaw)

    A characterization of half-positionality for omega-regular languages

    In the context of infinite duration games over graphs, a central question is: For which objectives can the existential player always play optimally using positional (memoryless) strategies? In this talk, we characterize omega-regular objectives with this property. Using this characterization, we obt...

  • 2023-11-29, 14:15, 5050

    Ruiwen Dong (Saarland University)

    Decidability problems in infinite semigroups

    This talk is about several algorithmic problems for matrix semigroups. A classic problem in this area is the well-known Semigroup Membership problem: given as input a finite set of square matrices S = {A1, A2, ... Ak} and a matrix A, decide whether there exists a sequence of matrices from S whose pr...

  • 2023-11-22, 14:15, 5050

    Rafał Stefański (University of Warsaw)

    Recognisable transducers over monads and comonads

    In 2015, Bojańczyk introduced a class of recognizable languages over monads, which is a common generalization of regular languages for many different types of objects, including words, infinite words, and trees. In this talk, I am going to extend this definition to transducers. As it turns out, the...

  • 2023-11-08, 14:15, 5050

    Michał Przybyłek (Polish-Japanese Academy of Information Technology)

    Some remarks on Stone-Čech compactification in ZFA

    Working in Zermelo-Fraenkel Set Theory with Atoms over an \omega-categorical \omega-stable structure, we show how some infinite constructions over definable sets can be encoded as finite constructions over Stone-Čech compactification of the sets. In particular, we show that for a definable set X wi...

  • 2023-10-25, 14:15, 5050

    Arka Ghosh (University of Warsaw)

    Equivariant polynomial ideals

    In this joint work with Sławek Lasota we study ideals of polynomials, where variables are elements of a countable logical structure. In this setting we allow structure-preserving embeddings to act on polynomials by renaming variables, and focus on ideals of polynomials which are equivariant, i.e., ...

  • 2023-10-18, 14:15, 5050

    Aliaume Lopez (University of Warsaw)

    From Local to Global Relativization of the Łoś–Tarski Theorem

    We consider first order sentences over a finite relational signature σ. Classical preservation theorems, dating back to the 1950s, state the correspondence between syntactic fragments of FO[σ], and semantic ones. The archetypal example of such preservation theorem is the Łoś–Tarski Theorem, th...

  • 2023-10-11, 14:15, 5050

    Mikołaj Bojańczyk (University of Warsaw)

    Polyregular functions on unordered trees of bounded height

    Joint work with Bartek Klin (University of Oxford) We consider first-order interpretations that input and output trees of bounded height. The corresponding functions have polynomial output size, since a first-order interpretation can use a $k$-tuple of input nodes to represent a single output nod...

  • 2023-10-04, 14:15, 5050

    Filip Mazowiecki (University of Warsaw)

    Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality

    Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodings (Lipton, '76). More precisely, Rosier and Yen later utilise Rackoff's bounding technique to show that if coverabilit...

  • 2023-09-06, 14:15, 5050

    Uli Fahrenberg ( EPITA Rennes & Paris)

    Higher-dimensional automata theory

    I will give a gentle introduction to higher-dimensional automata (HDAs) and their language theory. HDAs have been introduced some 30 years ago as a model for non-interleaving concurrency which generalizes, for example, Petri nets while retaining some automata-theoretic intuition. They have been stud...

  • 2023-07-05, 14:15, 5050

    Michał Gajda (MigaMake Pte Ltd, Singapur)

    Semigroup decomposition and semigroup transformers

    Krohn-Rhodes theorem claims that every semigroup can be decomposed into finite groups, and aperiodic semigroups. This theorem has been generalized from finite semigroups to infinite ones, but uses a hairy construct of a wreath product, and is rather hard to follow in its full grace (over hundred pag...