{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:40Z","timestamp":1725455440841},"publisher-location":"Berlin\/Heidelberg","reference-count":25,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016285","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T00:39:17Z","timestamp":1131842357000},"page":"582-593","source":"Crossref","is-referenced-by-count":0,"title":["The parallel complexity of deadlock detection"],"prefix":"10.1007","author":[{"given":"Paul","family":"Spirakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"56_CR1","volume-title":"Operating Systems Theory","author":"E.G. Coffman","year":"1973","unstructured":"E.G. Coffman and P.J. Denning.: \"Operating Systems Theory\" Prentice-Hall, Englewood Cliffs, New Jersey, 1973."},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"E.W. Dijkstra.: \"Solution of a Problem in Concurrent Programming Control\", CACM, Vol. B., No 9, Sept. 1965.","DOI":"10.1145\/365559.365617"},{"issue":"2","key":"56_CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0020-0190(79)90152-2","volume":"9","author":"D. Dobkin","year":"1979","unstructured":"Dobkin D., R.J. Lipton and S. Reiss.: \"Linear Programming is log-space hard for P\", Information Processing Lett. 9(2), 96\u201397, 1979.","journal-title":"Information Processing Lett."},{"key":"56_CR4","doi-asserted-by":"crossref","unstructured":"Dymond P.W. and M. Tompa.: \"Speedups of determinstic machines by synchronous parallel machines\", Proc. 15th Symp. on Theory of Computing, Boston M.A., April 1983.","DOI":"10.1145\/800061.808763"},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"V.D. Gligor and S.H. Shattuck.: \"On Deadlock Detection in Distributed Systems\", IEEE Trans. on Software Engineering, Vol. SE-6. No 5, Sept. 1980.","DOI":"10.1109\/TSE.1980.230491"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"E.M. Gold.: \"Deadlock Prediction: Easy and Difficult Cases\", Vol. 7, No. 3 Aug. 1978.","DOI":"10.1137\/0207027"},{"key":"56_CR7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L.M. Goldschlager","year":"1982","unstructured":"Goldschlager L.M., R.A. Show and J. Staples.: \"The maximum flow problem is log-space complete for P\", Theoretical Computer Science, 21 105\u2013111, 1982.","journal-title":"Theoretical Computer Science"},{"key":"56_CR8","doi-asserted-by":"crossref","unstructured":"A.N. Habermann.: \"Prevention of System Deadlock\", CACM, Vol. 12, No. 7, July 1969.","DOI":"10.1145\/363156.363160"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"R.C. Holt.: \"Comments on Prevention of Systems Deadlocks\", CACM, Vol. 14, No. 1, Jan. 1971.","DOI":"10.1145\/362452.362486"},{"key":"56_CR10","unstructured":"R.C. Holt.: \"On Deadlock in Computer Systems\", Ph.D. Thesis, Cornell Unic., 1971."},{"key":"56_CR11","doi-asserted-by":"crossref","unstructured":"R.C. Holt.: \"Some Deadlock Properties of Computer Systems\", Computing Surveys, Vol. 4, No. 3, Sept. 1972.","DOI":"10.1145\/356603.356607"},{"key":"56_CR12","unstructured":"J.Ja'Ja'.: \"Parallel Graph Algorithms\", Tech. Report, Penn. State University, 1978."},{"issue":"1","key":"56_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1976","unstructured":"Jones N.D. and W.T. Laaser.: \"Complete problems for deterministic polynomial time\", Theort. Comput. Sci. 3(1), 105\u2013117, 1976.","journal-title":"Theort. Comput. Sci."},{"key":"56_CR14","doi-asserted-by":"crossref","unstructured":"T. Kameda.: \"Testing Deadlock-Freedom of Computer Systems\", JACM, Vol. 27, No.2. Apr. 1980.","DOI":"10.1145\/322186.322192"},{"issue":"1","key":"56_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner R.E.: \"The Circuit value problem is log-space complete for P\", SIGACT news 7(1), 18\u201320 (1975).","journal-title":"SIGACT news"},{"key":"56_CR16","doi-asserted-by":"crossref","unstructured":"D. Menasce and R.R. Muntz.: \"Locking and Deadlock Detection in Distributed Data Bases\", IEEE Trans. on Software Eng., Vol. SE-5, No. 3 May 1979.","DOI":"10.1109\/TSE.1979.234181"},{"key":"56_CR17","doi-asserted-by":"crossref","unstructured":"T. Minoura.: \"Deadlock Avoidance Revisited\", JACM, Vol. 24, No.4 Oct. 1982.","DOI":"10.1145\/322344.322351"},{"key":"56_CR18","doi-asserted-by":"crossref","unstructured":"R. Obermark.: \"Distributed Deadlock Detection Algorithm\", ACM TODS, Vol. 7, No.2, June 1982.","DOI":"10.1145\/319702.319717"},{"key":"56_CR19","unstructured":"J. Peterson and A. Silberchatz.: \"Operating System Concepts\", Addison-Welsey, 1983."},{"key":"56_CR20","doi-asserted-by":"crossref","unstructured":"Reif J.H.: \"On the power of probabilistic choice in synchronous parallel computations\", 9th International Colloquium on Automata, Languages and Programming, Aarthus, Denmark, 442\u2013450, July 1982.","DOI":"10.1007\/BFb0012790"},{"key":"56_CR21","doi-asserted-by":"crossref","unstructured":"D.G. Rosenkrantz, R.E. Stearns and Lewis P.M.: \"System Level Concurrency Control for Distributed Database Systems\", ACM TODS, Vol. 3, No.2, June 1978.","DOI":"10.1145\/320251.320260"},{"key":"56_CR22","doi-asserted-by":"crossref","unstructured":"Savage C. and J. Ja'Ja'.: Fast Efficient Parallel algorithms for some graph problems\", SIAM J. Comp. 10(4), 1981.","DOI":"10.1137\/0210051"},{"key":"56_CR23","doi-asserted-by":"crossref","unstructured":"J. Schwartz.: \"Ultracomputers\", ACM Transactions on Programming Languages and System, 1980.","DOI":"10.1145\/357114.357116"},{"key":"56_CR24","volume-title":"The Logical Design of Operating Systems","author":"A.C. Shaw","year":"1974","unstructured":"A.C. Shaw.: \"The Logical Design of Operating Systems\", Prentice Hall, Englewood Cliffs, N.J. 1974."},{"key":"56_CR25","unstructured":"Wyllie J.C.: \"The Complexity of Parallel Computations\", Ph. D. Thesis and Tch. Report 79-387, Dept. of C.S. Cornell Univ. 1979."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016285.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:36:02Z","timestamp":1607531762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0016285","relation":{},"subject":[]}}