 You are not logged in | log in |
| You are not logged in | log in |
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...
