{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:10:12Z","timestamp":1737360612172,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_31","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"323-334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies"],"prefix":"10.1007","author":[{"given":"V. L.","family":"Selivanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz and J. Gabarr\u00f3. Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz and J. Gabarr\u00f3. Structural Complexity II, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. P. Bovet","year":"1992","unstructured":"D. P. Bovet, P. Crescenzi and R. Silvestri. A uniform approach to define complexity classes. Theoret. Comp. Sci, 104 (1992), 263\u2013283.","journal-title":"Theoret. Comp. Sci"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0022-0000(78)90049-1","volume":"16","author":"J. A. Brzozowski","year":"1978","unstructured":"J. A. Brzozowski and R Knast. The dot-depth hierarchy of star-free languages is infinite. J. Comp. Systems Sci., 16 (1978), 37\u201355.","journal-title":"J. Comp. Systems Sci."},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"H.-J. Burtschick","year":"1998","unstructured":"H.-J. Burtschick and H. Vollmer. Lindstr\u00f6m Quatifiers and Leaf Language Definability. Int. J. of Foundations of Computer Science, 9 (1998), 277\u2013294.","journal-title":"Int. J. of Foundations of Computer Science"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer and K. W. Wagner. On the power of polynomial time bit-reductions, Proc. 8th Structure in Complexity Theory, 1993, 200\u2013207.","DOI":"10.1109\/SCT.1993.336526"},{"key":"31_CR7","unstructured":"K. Kuratowski and A. Mostowski. Set Theory. North Holland, 1967."},{"key":"31_CR8","volume-title":"The difference and truth-table hierarchies for NP","author":"J. K\u00f6bler","year":"1986","unstructured":"J. K\u00f6bler, U. Sh\u00f6ning and K.W. Wagner: The difference and truth-table hierarchies for NP. Dep. of Informatics, Koblenz. Preprint 7 (1986)."},{"key":"31_CR9","volume-title":"Counter-free automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton and S. Papert. Counter-free automata. MIT Press, Cambridge, Massachusets, 1971."},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0022-0000(86)90037-1","volume":"32","author":"D. Perrin","year":"1986","unstructured":"D. Perrin and J.-E. Pin. First order logic and star-free sets. J. Comp. and Syst. Sci., 32 (1986), 393\u2013406.","journal-title":"J. Comp. and Syst. Sci."},{"key":"31_CR11","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF02679467","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"J.-E. Pin and P. Weil. Polynomial closure and unambiguous product. Theory of Computing Systems, 30 (1997), 383\u2013422.","journal-title":"Theory of Computing Systems"},{"key":"31_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/3-540-57785-8_161","volume-title":"Proc. of Symposium on Theor. Aspects of Computer Science STACS-94","author":"V. L. Selivanov","year":"1994","unstructured":"V. L. Selivanov. Two refinements of the polynomial hierarchy. In: Proc. of Symposium on Theor. Aspects of Computer Science STACS-94, Lecture Notes in Computer Science, v. 775. Springer: Berlin 1994, p. 439\u2013448."},{"key":"31_CR13","unstructured":"V. L. Selivanov. Refining the polynomial hierarchy, Preprint No 9, the University of Heidelberg, Chair of Mathematical Logic, 1994, 20 p."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/2275522","volume":"60","author":"V. L. Selivanov","year":"1995","unstructured":"V. L. Selivanov. Fine hierarchies and Boolean terms. Journal of Symbolic Logic, 60 (1995), p. 289\u2013317.","journal-title":"Journal of Symbolic Logic"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/BF02671730","volume":"38","author":"V. L. Selivanov","year":"1999","unstructured":"V. L. Selivanov. Refining the polynomial hierarchy. Algebra and Logic, 38 (1999), 456\u2013475 (Russian, there is an English translation).","journal-title":"Algebra and Logic"},{"key":"31_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/3-540-44693-1_47","volume-title":"Proc. of 18-th Int. Symposium on Theor. Aspects of Computer Science STACS-2001 in Dresden, Germany","author":"V. L. Selivanov","year":"2001","unstructured":"V. L. Selivanov. A logical approach to decidability of hierarchies of regular star-free languages. In: Proc. of 18-th Int. Symposium on Theor. Aspects of Computer Science STACS-2001 in Dresden, Germany, Lecture Notes in Computer Science, v. 2010. Berlin: Springer, 2001, 539\u2013550."},{"key":"31_CR17","unstructured":"V. L. Selivanov and A. G. Shukin. On hierarchies of regular star-free languages (in Russian). Preprint 69 of A.P. Ershov Institute of Informatics Systems, 2000, 28 p."},{"key":"31_CR18","first-page":"141","volume":"161","author":"A. G. Shukin","year":"1998","unstructured":"A. G. Shukin. Difference hierarchies of regular languages. Comp. Systems, Novosibirsk, 161 (1998), 141\u2013155 (in Russian).","journal-title":"Comp. Systems"},{"key":"31_CR19","unstructured":"H. Schmitz and K. W Wagner. The Boolean hierarchy over level 1\/2 of the Sraubing-Therien hierarchy, Technical Report 201, Inst. f\u00fcr Informatik, Univ. W\u00fcrzburg (available at http:\/\/www.informatik.uni-wuerzburg.de )."},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"W. Thomas. Classifying regular events in symbolic logic. J. Comp. and Syst. Sci., 25 (1982), 360\u2013376.","journal-title":"J. Comp. and Syst. Sci."},{"key":"31_CR21","first-page":"51","volume":"57","author":"N. K. Vereshchagin","year":"1993","unstructured":"N. K. Vereshchagin. Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk, 57 (1993), 51\u201390 (in Russian).","journal-title":"Izvestiya Rossiiskoi Akademii Nauk"},{"key":"31_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BFb0028832","volume-title":"Proceedings of the 1985 Int. Conf. on Fundamentals of Computation theory","author":"G. Wechsung","year":"1985","unstructured":"G. Wechsung and K. Wagner. On the Boolean closure of NP. In: Proceedings of the 1985 Int. Conf. on Fundamentals of Computation theory, v.199 of Lecture Notes in Computer Science, p.485\u2013493. Springer-Verlag, 1985."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T07:28:00Z","timestamp":1737358080000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_31","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"2 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}