Weekly research seminar

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)

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