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:

  1. Reachability problem for 3-dimensional VASSes - complexity
    (the best algorithm known is in F7, i.e. beyond Tower, PSpace-hardness known)
  2. Reachability problem for fixed VASS - complexity
    (in between Ackermann and NL-hard)
  3. Length of the shortest covering run for VASS - parametrized complexity
    (it is polynomial by Rackoff, but is it in FPT parametrized by the dimension?)
  4. Reachability problem for automaton with one counter and one stack - decidability
    (decidability not known, only PSpace-hardness known)
  5. Regular separability for languages of Vector Addition Systems - decidability
    (decidability known for many subclasses)
  6. Regular separability for languages of 2-dimensional Vector Addition Systems - decidability
    (one of simplest subclasses for which decidability is not known)
  7. Coverability problem for automaton with one counter and one stack - complexity
    (ExpSpace algorithm known, only PSpace-hardness known)
  8. Reachability problem for two-dimensional Branching Vector Addition Systems - decidability
    (decidability known for dimension one and for coverability in any dimension)
  9. Equivalence problem for unambiguous pushdown automata - decidability
    (decidability known for deterministic case - famous result by Sénizergues)
  10. Language equivalence problem for unambiguous one-counter automata - decidability, complexity
    (deterministic case is in NL, nondeterministic case is undecidable)
  11. 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)
  12. Separability of nondeterministic register automata by deterministic register automata - decidability
    (case of separability by deterministic register automaton with fixed number of registered is decidable)
  13. 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)
  14. Multiplicity equivalence for One Counter Nets (1-VASSes) - decidability
    (this may be more achievable)
  15. 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.