Main categories of the problems studied are:
reachability and coverability problems
separability problems
equivalence problems (language, bisimulation, multiplicity equivalence)
Below some discussion on these problems. I'd be happy to discuss any of these, don't hesitate to contact me if you're interested in it.
The reachability and coverability problem for VASS and similar model still remain not understood despite the fact that its complexity is now knonw to be Ackermann-complete. There are a few directions, which are in my opinion very interesting, worth investigation and the progress is possible.
The first type is problems is understanding small dimensions. It becomes much clearer that there is still something important to find when we look at the small dimensions. Here the problems 1-4 belong. Some discussion below.
The upper bound for 3-dimensional VASS (shortly 3-VASS) was for a long time F7 (where Fi are classes from the fast-growing hierarchy of complexities, so-called Grzegorczyk hierarchy). It was however clear that any KLM-style algorithm cannot go below Tower complexity, as for any k ∈ N it is easy to construct 3-VASS, which for a given source have k-fold exponential reachability set. KLM-style algorithms explore the whole reachability set, so they cannot get below Tower. On the other hand, even for binary encoded VASS, the best lower bound is PSpace-hardness, inherited from PSpace-hardness for binary 2-VASS (Blondin. et. al., 2015). We have managed in 2025 to show a 2-ExpSpace upper bound for binary 3-VASS arxiv.org/abs/2502.13916. We have shown it by proving that existence of a run from s to t implies existance of a run of length at most triply-exponential. The key idea in the proof was to upper-approximate reachability set from s by some appropriately small semilinear set. In that we instead of exponential blowup for every added SCC of a VASS we've managed to get a polynomial blowup (for some polynomial of big degree), which resulted in the 3-exp bound. However, the 2-ExpSpace upper bound does not seem optimal. It looks like ExpSpace membership should be possible to obtain. Maybe even PSpace: currently we don't know any example of 3-VASS in which there is a run from s to t, but no run of at most exponential size. If there is always a run of at most exponential size, then the naive PSpace algorithm would work, which is actually very prosible. The question is: how to prove it? Or maybe: how to construct an example with the shortest path from s to t being at least doubly-exponential. This question, namely complexity of reachability for 3-VASS is a part of bigger question about low dimensions. A related, intriguing question is for which dimensions d reachability for d-VASS is elementary. We currently know Tower-hardness for 8-VASS arxiv.org/abs/2203.04243, but this is probably not optimal. What about reachability for 4-VASS, 5-VASS, 6-VASS and 7-VASS. We either need better techniques for Tower lower bounds, or better understanding of the structure of VASS runs, which would allow to show elementary algorithms. Both directions seem very challenging.
Another natural question is to ask what happens if we add integer counters (Z-counters) to a low dimensional VASS. It is clear that a VASS extended with integer counters (we just add to VASS a bunch of Z-counters) can be simulated by a VASS. Naively you just simulate a Z-counter y as a difference of two N-counters x1, x2, having simply y = x1-x2 allows both to increase and decrease y. This naive simulation allows to simulate k Z-counters by 2k N-counters. A bit less naively we can simulate k Z-counters y1, ..., yk by k+1 N-counters x, x1, ..., xk, just as yi = x - xi. However, this would still only place reachability problem for d-VASS+Z (d-dimensional VASS extended with an arbitrary number of integer counters) in Ackermann, for any d, even d = 1. Recently we analyse this problem in a paper which soon will appear on arXiv. It is easy to show that reachability for binary 1-VASS+Z is in PSpace, we even show NP. Interestingly we show that for any d, reachability in d-VASS+Z is in F_{d+2}. Can it get better? Probably yes. For the lower bounds, we show that reachability in unary 3-VASS+Z is Tower-hard and in unary 2-VASS+Z is PSpace-hard. The most interesting of these seems to be the problem for 2-VASS+Z. It is natural to conjecture that it is elementary, but how to show it? The hardest example we have is an example in which the shortest run from source s to target t is of 2-exp length. It is reasonable to conjecture that if there is some run there is also some of at most 2-exp length, which would give ExpSpace membership. Even that would leave a gap in between PSpace and ExpSpace. The model is pretty simple, but still the reachability set can be non semilinear (see the classical example by Hopcroft-Pansiot), which makes the analysis challenging, but also interesting.
Reachability problem for 3-dimensional VASSes - complexity (the best algorithm known is in 2ExpSpace, PSpace-hardness known)
Reachability problem for 2-dimensional VASSes extended with integer counters - complexity (the best algorithm known is in F4, PSpace-hardness known)
Reachability in 2-dimensional VAS (gap in between NP-hardness and PSpace)
Reachabiiity in exp-bounded 1-dimensional VAS (gap in between NP-hardness and PSpace)
Reachability in 2-exp bounded 2-counter automaton - complexity (obvious ExpSpace algorithm, PSpace-hardness known), the challenge is to deal with 2 counters, ExpSpace-hardness follows easily for 3 counters by the standard reduction from Turing Machines
Reachability problem for fixed binary VASS - complexity (in between Ackermann and PSpace-hardness)
Length of the shortest covering run for VASS - parametrized complexity (it is polynomial by Rackoff, but is it in FPT parametrized by the dimension?, or maybe linear for fixed VASS?)
Reachability problem for automaton with one counter and one stack - decidability (in between decidability and PSpace-hardness)
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 - complexity (decidability known, but complexity open)
F-separability for subclasses G of languages of Vector Addition Systems - decidability (not studied much, many open problems for F = LT, LTT, FO, FO2, G = VASS, Z-VASS, 1-VASS, cover. VASS etc.)
Separability of nondeterministic register automata by deterministic register automata - decidability (case of separability by deterministic register automaton with fixed number of registered is decidable)
Equivalence problem for unambiguous pushdown automata - decidability (decidability known for deterministic case - famous result by Sénizergues)
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)
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)
Multiplicity equivalence for BPP - complexity (2ExpSpace known)