{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:26:13Z","timestamp":1787387173132,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540160786","type":"print"},{"value":"9783540397588","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16078-7_85","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:37:19Z","timestamp":1330195039000},"page":"306-320","source":"Crossref","is-referenced-by-count":4,"title":["Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \u03c9-machines"],"prefix":"10.1007","author":[{"given":"Louis E.","family":"Rosier","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsu-Chun","family":"Yen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"25_CR1","first-page":"127","volume":"1","author":"J. Bentley","year":"1983","unstructured":"Bentley, J., Ottmann, T. and Widmayer, P., The complexity of manipulating hierarchically defined sets of rectangles, Advances in Computing Research, JAI Press Inc., Vol. 1, 1983, pp. 127\u2013158.","journal-title":"Advances in Computing Research"},{"issue":"1","key":"25_CR2","doi-asserted-by":"publisher","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":"25_CR3","unstructured":"Chang, C., Gouda, M. and Rosier, L., Deciding liveness for special classes of communicating finite state machines, Proc. of the 22nd Annual Allerton Conf. on Communication, Control, and Computing, 1984, pp. 931\u2013939."},{"key":"25_CR4","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0022-0000(77)80004-4","volume":"15","author":"R. Cohen","year":"1977","unstructured":"Cohen, R. and Gold, A., Theory of \u03c9-languages. I: Characterizations of \u03c9-Context-Free languages, J. of Computer and System Sciences, 15, 1977, pp. 169\u2013184.","journal-title":"J. of Computer and System Sciences"},{"key":"25_CR5","first-page":"78","volume":"LNCS 158","author":"S. Cook","year":"1983","unstructured":"Cook, S., The classification of problems which have fast parallel algorithms, Fundamentals of Computation Theory, LNCS 158, 1983, pp. 78\u201393.","journal-title":"Fundamentals of Computation Theory"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S., The complexity of theorem proving procedures, Proc. of the 3rd Annual ACM Symp. on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Emerson, E. and Lei, C., Modalities for model checking: branching time strikes back, Proc. of the 12th Annual ACM Symp. on Principles of Programming Languages, 1985, pp. 84\u201395.","DOI":"10.1145\/318593.318620"},{"key":"25_CR8","unstructured":"Emerson, E. and Lei, C., Temporal model checking under generalized fairness constraints, Proc. of the 18th Annual Hawaii Int. Conf. on System Sciences, 1985, pp. 277\u2013288."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(83)90107-2","volume":"17","author":"M. Fischer","year":"1983","unstructured":"Fischer, M. and Paterson, M., Storage requirements for fair scheduling, Information Processing Letters, 17, 1983, pp. 249\u2013250.","journal-title":"Information Processing Letters"},{"key":"25_CR10","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."},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Gouda, M. and Chang, C., A technique for proving liveness of communicating finite state machines with examples, Proc. of the 3rd Annual ACM Symp. on Principles of Distributed Computing, 1984, pp. 38\u201349.","DOI":"10.1145\/800222.806734"},{"key":"25_CR12","unstructured":"Gouda, M. and Rosier, L., On deciding progress for a class of communication protocols, Proc. of the 18th Annual Conf. on Information Sciences and Systems, Princeton Univ., 1984, pp. 663\u2013667."},{"key":"25_CR13","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":"25_CR14","doi-asserted-by":"publisher","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"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. Jones","year":"1976","unstructured":"Jones, N., Lien, E. and Laaser, W., New problems complete for nondeterministic log space, Mathematical Systems Theory, 10, 1976, pp. 1\u201317.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R., Reducibility among combinatorial problems, in Complexity of Computer Computations, edited by R. E. Miller and J. Thatcher, Plenum Press, New York, 1972, pp. 85\u2013104."},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"Ladner, R. and Lynch, N., Relativization of questions about log space computability, Mathematical Systems Theory, 10, 1976, pp. 19\u201332.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BF01691063","volume":"3","author":"L. Landweber","year":"1969","unstructured":"Landweber, L., Decision Problems for \u03c9-automata, Mathematical Systems Theory, 3, 1969, pp. 376\u2013384.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR19","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":"Automata, Languages and Programming"},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/3-540-10003-2_85","volume":"85","author":"H. Lewis","year":"1980","unstructured":"Lewis, H. and Papadimitriou, C., Symmetric space-bounded computation, Automata, Languages and Programming, LNCS 85, 1980, pp. 374\u2013384.","journal-title":"Automata, Languages and Programming"},{"key":"25_CR21","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":"25_CR22","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0304-3975(78)90003-8","volume":"6","author":"N. Lynch","year":"1978","unstructured":"Lynch, N., Log space machines with multiple oracle tapes, Theoretical Computer Science, 6, 1978, pp. 25\u201339.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"25_CR23","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1145\/62.322435","volume":"31","author":"C. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C., On the complexity of unique solutions, JACM, Vol. 31, No. 2, April 1984, pp. 392\u2013400.","journal-title":"JACM"},{"key":"25_CR24","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"Papadimitriou, C. and Yannakakis, M., The complexity of facets (and some facets of complexity), J. of Computer and System Sciences, 28, 1984, pp. 244\u2013259.","journal-title":"J. of Computer and System Sciences"},{"issue":"2","key":"25_CR25","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J. Reif","year":"1984","unstructured":"Reif, J., Symmetric complementation, JACM, Vol. 31, No. 2, April 1984, pp. 401\u2013421.","journal-title":"JACM"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Rosier, L. and Yen, H., Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \u03c9-machines, Univ. of Texas at Austin, Dept. of Computer Sciences, Tech. Report No. 85-08, May 1985.","DOI":"10.1007\/3-540-16078-7_85"},{"key":"25_CR27","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":"25_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"Stockmeyer, L., The polynomial-time hierarchy, Theoretical Computer Science, 3, 1977, pp. 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"25_CR29","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","STACS 86"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16078-7_85.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:25:20Z","timestamp":1742588720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16078-7_85"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540160786","9783540397588"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-16078-7_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}