{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:06Z","timestamp":1725663066277},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_83","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:52:36Z","timestamp":1330195956000},"page":"334-343","source":"Crossref","is-referenced-by-count":3,"title":["On the complexity of deciding fair termination of probabilistic concurrent finite-state programs"],"prefix":"10.1007","author":[{"given":"Louis E.","family":"Rosier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsu-Chun","family":"Yen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"issue":"2","key":"35_CR1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/62.322433","volume":"31","author":"A. Adachi","year":"1984","unstructured":"Adachi, A. and Iwata, S., Some combinatorial game problems require \u03a9(nk) time, JACM, Vol. 31, No. 2, April 1984, pp. 361\u2013376.","journal-title":"JACM"},{"issue":"1","key":"35_CR2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"Chandra, A., Kozen, D. and Stockmeyer, L., Alternation, JACM, Vol. 28, No. 1, January 1981, pp. 114\u2013133.","journal-title":"JACM"},{"key":"35_CR3","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D., \"Computers and Intractability: A Guide to the Theory of NP-Completeness\", W. H. Freeman and Company, San Francisco, 1979."},{"issue":"3","key":"35_CR4","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1145\/2166.357214","volume":"5","author":"S. Hart","year":"1983","unstructured":"Hart, S., Sharir, M. and Pnueli, A., Termination of probabilistic concurrent programs, ACM Trans. on Programming Languages and Systems, Vol. 5, No. 3, July 1983, pp. 356\u2013380.","journal-title":"ACM Trans. on Programming Languages and Systems"},{"key":"35_CR5","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1137\/0213021","volume":"13","author":"S. Hart","year":"1984","unstructured":"Hart, S., Sharir, M. and Pnueli, A., Verification of probabilistic systems, SIAM J. of Computing, 13, 1984, pp. 292\u2013314.","journal-title":"SIAM J. of Computing"},{"key":"35_CR6","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J. and Ullman, J., \"Introduction to Automata Theory, Languages, and Computation\", Addison-Wesley, Reading, Mass., 1979."},{"key":"35_CR7","unstructured":"Iwata, S. and Kasai, T., Problem requiring k*log n deterministic space, Proc. 15th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge, 1984."},{"key":"35_CR8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"Jones, N. and Laaser, W., Complete problems for deterministic polynomial time, Theoretical Computer Science, 3, 1977, pp. 105\u2013117.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"35_CR9","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01699467","volume":"18","author":"T. Kasai","year":"1985","unstructured":"Kasai, T. and Iwata, S., Gradually intractable problems and nondeterministic log-space lower bounds, Mathematical Systems Theory, Vol. 18, No. 2, 1985, pp. 153\u2013170.","journal-title":"Mathematical Systems Theory"},{"key":"35_CR10","unstructured":"Kemeny, J., Snell, J. and Knapp, A., \"Denumerable Markov Chains\", D. van Nostrad Company, 1966."},{"key":"35_CR11","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0022-0000(80)90033-1","volume":"21","author":"R. Ladner","year":"1980","unstructured":"Ladner, R., The complexity of problems in systems of communicating sequential processes, J. of Computer and System Sciences, 21, 1980, pp. 179\u2013194.","journal-title":"J. of Computer and System Sciences"},{"key":"35_CR12","first-page":"264","volume":"115","author":"D. Lehmann","year":"1981","unstructured":"Lehmann, D., Pnueli, A and Stavi, J., Impartiality, justice and fairness: The ethics of concurrent termination, Automata, Languages and Programming, LNCS 115, 1981, pp. 264\u2013277.","journal-title":"LNCS"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Lehmann, D. and Rabin, M., On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proc. of the 10th ACM Symp. on Principles of Programming Languages, 1981, pp. 133\u2013138.","DOI":"10.1145\/567532.567547"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Lichtenstein, O. and Pnueli, A., Checking that finite state concurrent programs satisfy their linear specification, Proc. of the 12th Annual ACM Symp. on Principles of Programming Languages, 1985, pp. 97\u2013107.","DOI":"10.1145\/318593.318622"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"Pnueli, A., On the extremely fair treatment of probabilistic algorithms, Proc. of the 15th Annual ACM Symp. on Theory of Computing, 1983, pp. 278\u2013290.","DOI":"10.1145\/800061.808757"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"Rabin, M., N-process synchronization by 4*log2N-valued shared variable, Proc. of the 21st Annual Symp. on Foundations of Computer Science, 1980, pp. 407\u2013410.","DOI":"10.1109\/SFCS.1980.26"},{"key":"35_CR17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF00288965","volume":"17","author":"M. Rabin","year":"1982","unstructured":"Rabin, M., The choice coordination problem, Acta Informatica, 17, 1982, pp. 121\u2013134.","journal-title":"Acta Informatica"},{"key":"35_CR18","first-page":"361","volume":"199","author":"L. Rosier","year":"1985","unstructured":"Rosier, L. and Yen, H., A multiparameter analysis of the boundedness problem for vector addition systems, Fundamentals of Computation Theory, LNCS 199, 1985, pp. 361\u2013370. (To appear in J. of Computer and System Sciences, 1986.)","journal-title":"LNCS"},{"key":"35_CR19","first-page":"306","volume":"210","author":"L. Rosier","year":"1986","unstructured":"Rosier, L. and Yen, H., Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \u03c9-machines, Proc. of 3rd Annual Symp. on Theoretical Aspects of Computer Science, LNCS 210, 1986, pp. 306\u2013320.","journal-title":"LNCS"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"Rosier, L. and Yen, H., On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Univ. of Texas at Austin, Dept. of Computer Sciences, Tech. Report No. 85-22, October 1985.","DOI":"10.1007\/3-540-16761-7_83"},{"key":"35_CR21","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W. Ruzzo","year":"1984","unstructured":"Ruzzo, W., Simon, J. and Tompa, M., Space-bounded hierarchies and probabilistic computations, J. of Computer and System Sciences, 28, 1984, pp. 216\u2013230.","journal-title":"J. of Computer and System Sciences"},{"key":"35_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M., Automatic verification of probabilistic concurrent finite-state programs, Proc. of the 26th Annual Symposium on Foundations of Computer Science, 1985, pp. 327\u2013338.","DOI":"10.1109\/SFCS.1985.12"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_83.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T17:44:15Z","timestamp":1687283055000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_83"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_83","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}