{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:01Z","timestamp":1742617141552,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_169","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:20:35Z","timestamp":1330262435000},"page":"533-541","source":"Crossref","is-referenced-by-count":5,"title":["On the acceptance power of regular languages"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Borchert","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T.Baker, J.Gill, R.Solovay. Relativations of the P =?NP question, SIAM Journal of Computing 4, 1975, pp. 431\u2013442","journal-title":"SIAM Journal of Computing"},{"key":"43_CR2","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(91)90040-C","volume":"42","author":"R. Beigel","year":"1991","unstructured":"R.Beigel. Relativized Counting Classes: Relations among Thresholds, Parity and Mods, Journal of Computer and System Science 42, 1991, pp. 76\u201396","journal-title":"Journal of Computer and System Science"},{"key":"43_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R. Beigel","year":"1992","unstructured":"R.Beigel, J.Gill. Counting Classes: thresholds parity, mods, and fewness, Theoretical Computer Science 103, 1992, pp. 3\u201323","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"D.P.Bovet, P.Crescenzi, R.Silvestri. Complexity Classes and Sparse Oracles, Proceedings of the 6th Structure in Complexity Theory Conference, 1991, pp. 102\u2013108","key":"43_CR4","DOI":"10.1109\/SCT.1991.160248"},{"key":"43_CR5","doi-asserted-by":"crossref","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, R.Silvestri. A Uniform Approach to Define Complexity Classes, Theoretical Computer Science 104, 1992, pp. 263\u2013283","journal-title":"Theoretical Computer Science"},{"issue":"No.5","key":"43_CR6","first-page":"395","volume":"6","author":"T. Gundermann","year":"1987","unstructured":"T.Gundermann, G.Wechsung. Counting Classes with Finite Acceptance Types, Computers and Artificial Intelligence 6 No. 5, 1987, pp. 395\u2013409","journal-title":"Computers and Artificial Intelligence"},{"unstructured":"M.A.Harrison. Introduction to Switching and Automata Theory, Mc-Graw Hill, 1965","key":"43_CR7"},{"key":"43_CR8","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J. Hartmanis","year":"1988","unstructured":"J.Hartmanis, L.Hemachandra. Complexity classes without machines: On complete languages fo UP, Theoretical Computer Science 58, 1988, pp. 129\u2013142","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"J.Hastad. Almost Optimal Lower Bounds for Small Depth Circuits, Proceedings of the 18th ACM Symposium on Theory of Computing, 1986, pp. 6\u201320","key":"43_CR9","DOI":"10.1145\/12130.12132"},{"key":"43_CR10","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(90)90081-R","volume":"74","author":"U. Hertrampf","year":"1990","unstructured":"U.Hertrampf Relations among Mod-Classes, Theoretical Computer Science 74, 1990, pp. 325\u2013328","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"U.Hertrampf. Locally Definable Acceptance Types for Polynomial Time Machines, Proceedings 9th STAGS, 1992, pp. 199\u2013207","key":"43_CR11","DOI":"10.1007\/3-540-55210-3_184"},{"doi-asserted-by":"crossref","unstructured":"U.Hertrampf, CLautemann, Th. Schwentick, H.Vollmer, K.Wagner. On the Power of Polynomial Time Bit-Computations, Proceedings of the 8th Structure in Complexity Theory Conference, 1993, pp. 200\u2013207","key":"43_CR12","DOI":"10.1109\/SCT.1993.336526"},{"unstructured":"J.E.Hopcroft, J.D.Ullman. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979","key":"43_CR13"},{"issue":"2","key":"43_CR14","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0890-5401(91)90002-J","volume":"90","author":"K. Ko","year":"1991","unstructured":"K.Ko. Separating the low and high hierarchies by oracles, Information and Computation 90(2), 1991, pp. 156\u2013177","journal-title":"Information and Computation"},{"key":"43_CR15","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"R.E.Ladner. On the structure of polynomial time reducibility, Journal of the ACM 22, 1975, pp. 155\u2013171","journal-title":"Journal of the ACM"},{"key":"43_CR16","first-page":"23","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L.Stockmeyer. The polynomial-time Hierarchy, Theoretical Computer Science 3, 1977, pp. 23\u201333","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"A.Yao. Separating the Polynomial time Hierarchy by Oracles, Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 1\u201310","key":"43_CR17","DOI":"10.1109\/SFCS.1985.49"},{"key":"43_CR18","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0022-0000(88)90037-2","volume":"36","author":"S. Zachos","year":"1988","unstructured":"S.Zachos. Probabilistic Quantifiers and Games, Journal of Computer and System Sciences 36, 1988, pp. 433\u2013451","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:12:51Z","timestamp":1742595171000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_169","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}