{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:10:58Z","timestamp":1740240658584,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540240143"},{"type":"electronic","value":"9783540305507"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30550-7_8","type":"book-chapter","created":{"date-parts":[[2010,7,2]],"date-time":"2010-07-02T19:06:05Z","timestamp":1278097565000},"page":"89-101","source":"Crossref","is-referenced-by-count":2,"title":["The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Borchert","sequence":"first","affiliation":[]},{"given":"Klaus-J\u00f6rn","family":"Lange","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T.P. Baker","year":"1975","unstructured":"Baker, T.P., Gill, J., Solovay, R.: Relativizations of the P =? NP Question. SIAM J.\u00a0Computing\u00a04, 431\u2013442 (1975)","journal-title":"SIAM J.\u00a0Computing"},{"issue":"4","key":"8_CR2","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. Barrington","year":"1988","unstructured":"Barrington, D., Th\u00e9rien, D.: Finite Monoids and the Fine Structure of NC 1. J.\u00a0of the ACM\u00a035(4), 941\u2013952 (1988)","journal-title":"J.\u00a0of the ACM"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1051\/ita:1999116","volume":"33","author":"B. Borchert","year":"1999","unstructured":"Borchert, B., Kuske, D., Stephan, F.: On existentially first-order definable languages and their relation to NP. Theoret.\u00a0Informatics Appl.\u00a033, 259\u2013269 (1999)","journal-title":"Theoret.\u00a0Informatics Appl."},{"key":"8_CR4","unstructured":"Borchert, B., Schmitz, H., Stephan, F.: ${\\rm Leaf}^P(\\Delta_2^B) = \\Delta_2^p$ (1999) (unpublished manuscript)"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D.P. Bovet","year":"1992","unstructured":"Bovet, D.P., Crescenzi, P., Silvestri, R.: A uniform approach to define complexity classes. Theoretical Computer Science\u00a0104, 263\u2013283 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"8_CR6","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/S0097539799360148","volume":"30","author":"H. Buhrman","year":"2000","unstructured":"Buhrman, H., Torenvliet, L.: Randomness is Hard. SIAM J.\u00a0Computing\u00a030(5), 1485\u20131501 (2000)","journal-title":"SIAM J.\u00a0Computing"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1142\/S0129054198000180","volume":"9","author":"H.-J. Burtschick","year":"1998","unstructured":"Burtschick, H.-J., Vollmer, H.: Lindstr\u00f6m Quantifiers and Leaf Language Definability. International J.\u00a0of Foundations of Computer Science\u00a09, 277\u2013294 (1998)","journal-title":"International J.\u00a0of Foundations of Computer Science"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01744434","volume":"17","author":"H. Heller","year":"1984","unstructured":"Heller, H.: Relativized Polynomial Hierarchies Extending Two Levels. Mathematical Systems Theory\u00a017, 71\u201384 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Hertrampf, U., Lautemann, C., Schwentick, T., Vollmer, H., Wagner, K.: On the power of polynomial-time bit-computations. In: Proc. 8th Structure in Complexity Theory Conference, pp. 200\u2013207 (1993)","DOI":"10.1109\/SCT.1993.336526"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"Kadin, J.: The Polynomial Time Hierarchy collapses if the Boolean Hierarchy collapses. SIAM J.\u00a0Computing\u00a017, 1263\u20131282 (1988)","journal-title":"SIAM J.\u00a0Computing"},{"key":"8_CR11","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1990","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1990)"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Pin, J.-E.: Bridges for Concatenation Hierarchies. In: Proc.\u00a0Int.\u00a0Conf.\u00a0Automata, Languages and Programming, pp. 431\u2013442 (1998)","DOI":"10.1007\/BFb0055073"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0022-4049(88)90097-7","volume":"52","author":"J.-E. Pin","year":"1988","unstructured":"Pin, J.-E., Straubing, H., Th\u00e9rien, D.: Locally trivial categories and unambiguous concatenation. J.\u00a0of Pure and Applied Algebra\u00a052, 297\u2013311 (1988)","journal-title":"J.\u00a0of Pure and Applied Algebra"},{"key":"8_CR14","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/BF02679467","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"Pin, J.-E., Weil, P.: Polynomial closure and unambiguous product. Theory of Computing Systems\u00a030, 383\u2013422 (1997)","journal-title":"Theory of Computing Systems"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02194921","volume":"13","author":"M.P. Sch\u00fctzenberger","year":"1976","unstructured":"Sch\u00fctzenberger, M.P.: Sur le produit de concatenation non ambigu. Semigroup Forum\u00a013, 47\u201375 (1976)","journal-title":"Semigroup Forum"},{"key":"8_CR16","unstructured":"Schmitz, H., Wagner, K.W.: The Boolean hierarchy over level 1\/2 of the Straubing-Th\u00e9rien hierarchy, Technical report 201, Inst. f\u00fcr Informatik, Uni. W\u00fcrzburg (1998)"},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1051\/ita:2002003","volume":"36","author":"V.L. Selivanov","year":"2002","unstructured":"Selivanov, V.L.: Relating Automata-Theoretic Hierarchies to Complexity-Theoretic Hierarchies. RAIRO\u2013Theoretical Informatics & Applications\u00a036(1), 29\u201342 (2002)","journal-title":"RAIRO\u2013Theoretical Informatics & Applications"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Selivanov, V.L., Wagner, K.W.: A Reducibility for the Dot-Depth Hierarchy. In: Proc.\u00a0MFCS, pp. 783\u2013793 (2004)","DOI":"10.1007\/978-3-540-28629-5_61"},{"key":"8_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0289-9","volume-title":"Finite Automata, Formal Logic, and Circuit Complexity","author":"H. Straubing","year":"1994","unstructured":"Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkh\u00e4user, Boston (1994)"},{"issue":"1","key":"8_CR20","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00224-002-1035-9","volume":"36","author":"H. Straubing","year":"2003","unstructured":"Straubing, H., Th\u00e9rien, D.: Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. Theory Comput. Syst\u00a036(1), 29\u201369 (2003)","journal-title":"Theory Comput. Syst"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Tesson, P., Th\u00e9rien, D.: Diamonds are forever: the Variety DA. In: Semigroups, Algorithms, Automata and Languages, WSP, pp. 475\u2013499 (2002)","DOI":"10.1142\/9789812776884_0021"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K.W. Wagner","year":"1990","unstructured":"Wagner, K.W.: Bounded Query Classes. SIAM J.\u00a0Computing\u00a019, 833\u2013846 (1990)","journal-title":"SIAM J.\u00a0Computing"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Separating the Polynomial Hierarchy by oracles. In: Proc.\u00a026th IEEE Symp.\u00a0on the Foundations of Computer Science, pp. 1\u201310 (1985)","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30550-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T15:42:17Z","timestamp":1740238937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30550-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240143","9783540305507"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30550-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}