Allan Cheng
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Allan Cheng has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
Javier Esparza
Laboratory for Foundations of Computer Science University of Edinburgh The King's Buildings Edinburgh EH9 3JZ
1 shared publication- Jens Palsberg
Computer Science Department, Aarhus University, DK-8000 Aarhus C, Denmark
1 shared publication
Latest Publications
- 15 September 1997
- Published by Elsevier in Theoretical Computer Science
- Vol. 183 (2) , 229-251
Petri nets, traces, and local model checking
- 15 September 1997
- Published by Elsevier in Theoretical Computer Science
- Vol. 183 (2) , 229-251
Petri nets, traces, and local model checking
- Open Access
- 1 September 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (455)
Complexity Results for 1-safe Nets
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 PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-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. This paper is to be presented at FST & TCS, Foundations of Software Technology & Theoretical Computer Science, to be held 15-17 December 1993, in Bombay, India. A version of the paper with most proofs omitted is to appear in the proceedings.
- 1 September 1993
- Published by Det Kgl. Bibliotek/Royal Danish Library in DAIMI Report Series
- Vol. 22 (455)
Open AccessComplexity Results for 1-safe Nets
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 PSPACE-complete for 1-safe nets. We also prove that deadlock is NP-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. This paper is to be presented at FST & TCS, Foundations of Software Technology & Theoretical Computer Science, to be held 15-17 December 1993, in Bombay, India. A version of the paper with most proofs omitted is to appear in the proceedings.