Infinite Automata Workshop

Together with Filip Mazowiecki we organized in June 2024 a worshop about infinite-state systems Infinite Automata. The aim of the workshop was to discuss recent important progress in the field, interesting open problems and future directions and last, but not least, integrate our community. At the webpage you can find recordings, slides and photos from the event.

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 Tower, PSpace-hardness known)
  2. Reachability problem for fixed binary VASS - complexity
    (in between Ackermann and PSpace-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?, or maybe linear for fixed VASS?)
  4. Reachability problem for automaton with one counter and one stack - decidability
    (decidability not known, only PSpace-hardness known)
  5. 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.)
  6. Coverability problem for automaton with one counter and one stack - complexity
    (ExpSpace algorithm known, only PSpace-hardness known)
  7. Reachability problem for two-dimensional Branching Vector Addition Systems - complexity
    (decidability known, but complexity open)
  8. Reachability problem for Branching Vector Addition Systems - decidability
    (recently solved for dimension two, higher dimensions open)
  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.