Reference:

A. Cheng, J. Esparza, and J. Palsberg. Complexity results for 1-safe nets. Theoretical Computer Science, 147:117–136, 1995.

Abstract:

We study the complexity of several standard problems for 1-safe Petri nets and some of its subclasses. We prove that reachability, liveness and deadlock are all -complete for 1-safe nets. We also prove that deadlock is -complete for free-choice nets and for 1-safe free-choice nets. Finally, we prove that for arbitrary Petri nets, deadlock is equivalent to reachability and liveness.

Suggested BibTeX entry:

@article{CEP95,
    author = {A. Cheng and J. Esparza and J. Palsberg},
    journal = {Theoretical Computer Science},
    pages = {117--136},
    title = {Complexity results for 1-safe nets},
    volume = {147},
    year = {1995}
}