Optimal Label Splitting for Embedding an LTS into an arbitrary Petri Net Reachability Graph is NP-complete

Uli Schlachter, Harro Wimmel

For a given labelled transition system (LTS), synthesis is the task to find an unlabelled Petri net with an isomorphic reachability graph. Even when just demanding an embedding int…