Backwards-reachability for cooperating multi-pushdown systems

Chris Köcher, Dietrich Kuske

Abstract

A cooperating multi-pushdown system consists of a tuple of pushdown systems that can delegate the execution of recursive procedures to sub-tuples; control returns to the calling tuple once all sub-tuples finished their task. This allows the concurrent execution since disjoint sub-tuples can perform their task independently. Because of the concrete form of recursive descent into sub-tuples, the content of the multi-pushdown does not form an arbitrary tuple of words, but can be understood as a Mazurkiewicz trace. For such systems, we prove that the backwards reachability relation efficiently preserves recognizability, generalizing a result and proof technique by Bouajjani et al. for single-pushdown systems. It follows that the reachability relation is decidable for cooperating multi-pushdown systems in polynomial time and the same holds, e.g., for safety and liveness properties given by recognizable sets of configurations.
BibTeX
@article{kocher2025backwards,
  author = {Chris Köcher and Dietrich Kuske},
  title = {{Backwards-reachability for cooperating multi-pushdown systems}},
  journal = {J. Comput. Syst. Sci.},
  year = {2025},
  doi = {10.1016/j.jcss.2024.103601},
}

Loading related content...

Figure