## Friday Afternoon Seminar

Together with Filip Mazowiecki we organize Friday Afternoon Seminar. The aim of the seminar is to focus more on in-depth understanding of hard and technical, but inspiring results. The seminar takes place five times a year (every even numbered month except August in summer).

## Open problems in infinite-states systems

The field of infinite-state systems is full of unsolved problems, some of them remaining unsolved for decades. To inspire the research I present below a very subjective (and clearly not aspiring to be full) list of open problems, which seem to me to be interesting and may be a good next step in my opinion.

A very subjective list of problems, which seem important and may be currently in reach:

- Reachability problem for 3-dimensional VASSes - complexity

(the best algorithm known is in F7, i.e. beyond Tower, PSpace-hardness known) - Reachability problem for automaton with one counter and one stack - decidability

(decidability not known, only PSpace-hardness known) - Regular separability for languages of Vector Addition Systems - decidability

(decidability known for many subclasses) - Regular separability for languages of 2-dimensional Vector Addition Systems - decidability

(one of simplest subclasses for which decidability is not known) - Coverability problem for automaton with one counter and one stack - complexity

(ExpSpace algorithm known, only PSpace-hardness known) - Reachability problem for two-dimensional Branching Vector Addition Systems - decidability

(decidability known for dimension one and for coverability in any dimension) - Equivalence problem for unambiguous pushdown automata - decidability

(decidability known for deterministic case - famous result by Sénizergues) - Language equivalence problem for unambiguous one-counter automata - decidability, complexity

(deterministic case is in NL, nondeterministic case is undecidable) - Weak bisimilarity for BPA (PDA with one state) and its commutative version: BPP - decidability

(decidability is known for branching bisimulation, but weak seems to be very hard) - Separability of nondeterministic register automata by deterministic register automata - decidability

(case of separability by deterministic register automaton with fixed number of registered is decidable) - Multiplicity equivalence for context-free grammars (or pushdown automata) - decidability

(for each word both systems have the same number of accepting runs, no lower bound known, decidability conjectured) - Multiplicity equivalence for One Counter Nets (1-VASSes) - decidability

(this may be more achievable) - Multiplicity equivalence for Parikh automata (integer VASSes) - decidability

(for one letter alphabet it is in 2ExpTime)

Together with Georg Zetzsche and other people we manage a wikispaces with open problems concerning separability, look here. Currently there is no much life there.