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 fixed VASS - complexity
(in between Ackermann and NL-hard) - Length of the shortest covering run for VASS - parametrized complexity
(it is polynomial by Rackoff, but is it in FPT parametrized by the dimension?) - 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.