Backwards-reachability for cooperating multi-pushdown systems
Lists
Only you see this
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...