{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:17Z","timestamp":1787340677911,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1987,10]]},"abstract":"<jats:p>In this paper, we define a restricted logspace oracle hierarchy which turns out to be equivalent to the logspace alternation hierarchy (of Chandra, Kozen and Stockmeyer) and thus is contained within the second level of the logspace oracle heirarchy (of Ruzzo, Simon and Tompa). We then examine problems concerning various types of \u201cfair\u201d computations with respect to $\\omega $-Finite State Machines ($\\omega $-FSM\u2019s) and $\\omega $-One Counter Machines ($\\omega $-1CM\u2019s). For example, we consider the nonemptiness problem for $\\omega $-FSM\u2019s and $\\omega $-1CM\u2019s where acceptance is defined in the usual fashion, but with a fairness constraint imposed on accepting computations. Our results yield problems that are complete not only for LOGSPACE and PTIME but the second and third levels of the restricted logspace oracle hierarchy as well. As far as we know, these are the first natural problems shown to be complete for various levels of the logspace alternation hierarchy. The problems are also of independent interest. In fact, the nonemptiness problem (with fairness constraints) for w-machines has been shown to have immediate applications to the verification of concurrent finite state programs. Furthermore, the results can be used to strengthen known results concerning some related fairness problems that involve temporal logic (e.g. model checking).<\/jats:p>","DOI":"10.1137\/0216052","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:28:18Z","timestamp":1109226498000},"page":"779-807","source":"Crossref","is-referenced-by-count":9,"title":["Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\\omega $-Machines"],"prefix":"10.1137","volume":"16","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":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"J. Bentley, T. Ottmann, P. Widmayer,  The complexity of manipulating hierarchically defined sets of rectangles,  Advances in Computing Research 1, JAI Press,  1983,  127\u2013158","DOI":"10.1007\/3-540-10856-4_70"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"R3","unstructured":"C. Chang, M. Gouda, L. Rosier,  Deciding liveness for special classes of communicating finite state machines,  Proc. 22nd Annual Allerton Conf. on Communication, Control, and Computing,  1984,  931\u2013939"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80004-4"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Cook,  The complexity of theorem proving procedures,  Proc. 3rd Annual ACM Symposium on Theory of Computing,  1971,  151\u2013158 0253.68020","DOI":"10.1145\/800157.805047"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_95"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(87)90036-0"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90107-2"},{"key":"R9","volume-title":"Computers and intractability","author":"Garey M.","year":"1979"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. Gouda, C. Chang,  A technique for proving liveness of communicating finite state machines with examples,  Proc. 3rd Annual ACM Symp. on Principles of Distributed Computing,  1984,  38\u201349","DOI":"10.1145\/800222.806734"},{"key":"R11","unstructured":"M. Gouda, L. Rosier,  On deciding progress for a class of communication protocols,  Proc. 18th Annual Conf. on Information Sciences and Systems,  1984,  663\u2013667"},{"key":"R12","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft J.","year":"1979"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01752400"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90068-2"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683259"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683260"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691063"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10843-2_22"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10003-2_85"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"O. Lichtenstein, A. Pnueli,  Checking that finite state concurrent programs satisfy their linear specification,  Proc. 12th Annual ACM Symp. on Principles of Programming Languages,  1985,  97\u2013107","DOI":"10.1145\/318593.318622"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90003-8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/62.322435"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90068-0"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/62.322436"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"L. Rosier, H. Yen,  Logspace hierarchies, polynomial time and the complexity of fairness problems concerning  $\\omega$-machines, Rep., TR-85-08, Department of Computer Sciences, University of Texas at Austin, Austin, TX,  1985","DOI":"10.1007\/3-540-16078-7_85"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16761-7_83"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90066-7"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80005-5"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"M. Vardi,  Automatic verification of probabilistic concurrent finite-state programs,  Proc. 26th Annual Symposium on Foundations of Computer Science,  1985,  327\u2013338","DOI":"10.1109\/SFCS.1985.12"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0216052","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:47Z","timestamp":1787337827000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0216052"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,10]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1987,10]]}},"alternative-id":["10.1137\/0216052"],"URL":"https:\/\/doi.org\/10.1137\/0216052","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,10]]}}}