The theory of reachability in trace-pushdown systems

Dietrich Kuske

We consider pushdown systems that store, instead of a single word, a Mazurkiewicz trace on its stack. These systems are special cases of valence automata over graph monoids and sub…