We are happy to present Łukasz Kamiński’s talk titled “On decision problems in Petri nets with data”.
Petri nets with equality data is an extension of plain Petri nets where tokens carry values from an infinite data domain, and executability of transitions is conditioned by equalities between data values. The most fundamental decision problem for Petri nets, the reachability problem, asks, given a net together with source and target configurations, if there is a run from source to target. The decidability status of this problem for equality data still remains an intriguing open question. On the other hand, the coverability problem (where we ask if there is a run from source to a configuration that possibly extends target by some extra tokens) is decidable for equality data. The reachability is also decidable if we consider only reversible Petri nets. Furthermore, it was shown recently that the bi-reachability, a decision problem that is sandwiched between reachability and the two latter problems, is decidable.
One can also consider more complicated data domains, for instance ordered data. In this case reachability is undecidable, reachability in the reversible case and coverability are decidable and the decidability status of bi-reachability is an open question.
In this talk I will define Petri nets with data and discuss decision problems in this model.
Łukasz is a second year PhD student at the University of Warsaw and works under supervision of Sławek Lasota. His research concerns mainly vector addition systems and orbit-finite structures. He enjoys automata theory and logic in general.