Categories and Subject Descriptors: D.4.1 [Operating Systems]: Process Management; F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
General Terms: Algorithms, Theory
Additional Key Words and Phrases: NP-complete, PSPACE-complete
Selected references
- Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of the ACM, 28(1):114-133, January 1981.
- S. Even and R. E. Tarjan. A combinatorial problem which is complete in polynomial space. Journal of the ACM, 23(4):710-719, October 1976.
- Tiko Kameda. Testing deadlock-freedom of computer systems. Journal of the ACM, 27(2):270-280, April 1980.
- Thomas J. Schaefer. Complexity of decision problems based on finite two-person perfect-information games. In Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, pages 41-49, Hershey, Pennsylvania, 3-5 May 1976.
- A. Shoshani and E. G. Coffman. Sequencing tasks in multiprocess systems to avoid deadlocks. In Conference Record of 1970 Eleventh Annual Symposium on Switching and Automata Theory, pages 225-235, Santa Monica, California, 28-30 October 1970. IEEE.
- L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 1-9, Austin, Texas, 30 April-2 May 1973.
- Mihalis Yannakakis, C. H. Papadimitriou, and H. T. Kung. Locking policies: Safety and freedom from deadlock. In 20th Annual Symposium on Foundations of Computer Science, pages 286-297, San Juan, Puerto Rico, 29-31 October 1979. IEEE.