{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T20:07:00Z","timestamp":1794341220620,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540647812","type":"print"},{"value":"9783540686811","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055037","type":"book-chapter","created":{"date-parts":[[2006,8,1]],"date-time":"2006-08-01T08:08:05Z","timestamp":1154419685000},"page":"17-28","source":"Crossref","is-referenced-by-count":1,"title":["On existentially first-order definable languages and their relation to NP"],"prefix":"10.1007","author":[{"given":"Bernd","family":"Borchert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dietrich","family":"Kuske","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","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"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"55","author":"A. Blass","year":"1982","unstructured":"A. Blass, Y. Gurevich: On the unique satisfiability problem, Information and Control 55, 1982, pp. 80\u201388.","journal-title":"Information and Control"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0304-3975(95)00032-R","volume":"148","author":"B. Borchert","year":"1995","unstructured":"B. Borchert: On the acceptance power of regular languages, Theoretical Computer Science 148, 1995, pp. 207\u2013225.","journal-title":"Theoretical Computer Science"},{"key":"2_CR4","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, R. Silvestri: A uniform approach to define complexity classes, Theoretical Computer Science 104, 1992, pp. 263\u2013283.","journal-title":"Theoretical Computer Science"},{"key":"2_CR5","unstructured":"H.-J. Burtschick, H. Vollmer: Lindstr\u00f6m Quantifiers and Leaf Language Definability, ECCC Report TR96-005, 1996."},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J.-Y. Cai","year":"1988","unstructured":"J.-Y. Cai, T. Gondermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. Wagner, G. Wechsung: The Boolean Hierarchy I: structural properties, SIAM Journal on Computing 17, 1988, pp. 1232\u20131252","journal-title":"SIAM Journal on Computing"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1028","volume":"50","author":"R. Chang","year":"1995","unstructured":"R. Chang, J. Kadin, P. Hohatgi: On unique satisfiability and the threshold behavior of randomized reductions, Journal of Computer and System Science 50, 1995, pp. 359\u2013373.","journal-title":"Journal of Computer and System Science"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K. Wagner: On the power of polynomial-time bit-computations, Proc. 8th Structure in Complexity Theory Conference, 1993, pp. 200\u2013207","DOI":"10.1109\/SCT.1993.336526"},{"key":"2_CR9","volume-title":"Counter-Free Automata","author":"R. McNaughton","year":"1971","unstructured":"R. McNaughton, S. Papert: Counter-Free Automata, MIT Press, Cambridge, MA, 1971."},{"key":"2_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, J.-E. Pin: First-order logic and Star-free sets, J. of Computer and System Sciences 32, 1986, pp. 393\u2013406.","journal-title":"J. of Computer and System Sciences"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002240000058","volume":"30","author":"J.-E. Pin","year":"1997","unstructured":"J.-E. Pin, P. Weil: Polynomial closure and unambiguous product, Theory of Computing Systems 30, 1997, pp. 1\u201339.","journal-title":"Theory of Computing Systems"},{"key":"2_CR12","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":"H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkh\u00e4user, Boston, 1994."},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(82)90016-2","volume":"25","author":"W. Thomas","year":"1982","unstructured":"W. Thomas: Classifying regular events in symbolic logic, Journal of Computer and System Sciences 25, 1982, pp. 300\u2013376.","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda: PP is as hard as the Polynomial-Time Hierarchy, SIAM Journal on Computing 20, 1991, pp. 865\u2013877.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T02:59:24Z","timestamp":1736477964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540647812","9783540686811"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0055037","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0055035","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}