On Trace-Expressible Behaviour of Petri Nets

摘要

Abstract. We propose a trace-based approach to description behaviours of concurrent systems.nFirst, we define the independency relation induced by arbitrary transition system, forming this waynan asynchronous transition system. Then we introduce the notion of traceability of transition systemsnand study some decision problems, related to computing independency and deciding traceability fornbasic classes of Petri nets. Main results: traceability is decidable for place/transition nets and undecidablenin broader classes of nets – inhibitor, reset and transfer nets.