Cotygodniowe seminarium badawcze
2021-03-17, godz. 14:15, online
Mohnish Pattathurajan (MIM UW)
Parikh’s theorem for infinite alphabets
We investigate commutative images (Parikh Images) of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of finite ones. We prove the following. 1. Parikh Images of one-register...
2021-03-10, godz. 14:15, online
Pierre Ohlmann (IRIF, Université de Paris)
Controlling a random population
Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is dec...
2021-03-03, godz. 14:15, online
Szymon Toruńczyk (MIM UW)
Ordered graphs of bounded twin-width
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove that those are exactly the classes which avoid certain large grid-like structures as induced substructures...
2021-02-24, godz. 14:15, online
Filip Mazowiecki (Max Planck Institute for Software Systems)
Continuous One-Counter Automata
We study the reachability problem for continuous one-counter automata, COCA for short. In such automata, transitions are guarded by upper and lower bound tests against the counter value. Additionally, the counter updates associated with taking transitions can be (non-deterministically) scaled down b...
2021-01-20, godz. 14:15, online
Mikołaj Bojańczyk and Bartek Klin (MIM UW)
We develop the theory of vector spaces spanned by orbit-finite sets, with the main technical result being finite upper bounds on the lengths of increasing chains of equivariant subspaces. We then apply this theory to weighted register automata, which are a common generalization of weighted automata ...
2020-12-16, godz. 14:15, online
Denis Kuperberg (ENS Lyon)
Positive first-order logic on words.
I will present FO+, a restriction of first-order logic where letters are required to appear positively, and the alphabet is partially ordered (for instance by inclusion order if letters are sets of atoms). Restricting predicates to appear positively is for instance very natural when considering logi...
2020-12-09, godz. 14:15, online
Paweł Parys (MIM UW)
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation
We consider nested fixed-point expressions like µz.νy.µx.f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. Following a recent development for parity games, we show that a quasi-polynomial number of queries is sufficient, namely n^{lg(...
2020-12-02, godz. 14:15, online
Bartek Klin (MIM UW)
Nondeterministic and co-nondeterministic implies deterministic, for data languages.
I will explain why, if a data language and its complement are both recognized by non-deterministic register automata (without guessing), then they are both recognized by deterministic ones. The proof relies on the technology of sets with atoms. This is joint work with Sławek Lasota and Szymon Toru...
2020-11-25, godz. 14:15, online
Corentin Barloy (University of Lille)
Bidimensional linear recursive sequences and universality of unambiguous register automata
We study the universality and inclusion problems for register automata over equality data (A, =). We show that the universality and inclusion problems can be solved with 2-EXPTIME complexity when both automata are without guessing and unambiguous, improving on the currently best-known 2-EXPSPACE upp...
2020-11-18, godz. 14:15, online
Janusz Schmude (MIM UW)
Polynomial grammars with substitution
Polynomial grammars are grammars whose nonterminals generate tuples of integers (or elements of some ring in general) and productions use polynomial functions. They proved to be useful for proving decidability of equivalence of MSO transductions over strings and unordered trees and in general can be...