Collected by Wojciech Czerwiński
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.
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)