{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:04Z","timestamp":1742617084491,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-56503-5_47","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:16:11Z","timestamp":1330254971000},"page":"473-483","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Extended locally definable acceptance types"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Niedermeier","sequence":"first","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"R. Beigel, J. Gill, and U. Hertrampf. Counting classes: Threshold, parity, mods, and fewness. In Proc. of 7th STACS, number 415 in LNCS, pages 49\u201357. Springer, 1990.","DOI":"10.1007\/3-540-52282-4_31"},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"G. Buntrock, L. A. Hemachandra, and D. Siefkes. Using inductive counting to simulate nondeterministic computation. In Proc. of 15th MFCS, number 452 in LNCS, pages 187\u2013194. Springer, 1990. (to appear in Information and Computation).","DOI":"10.1007\/BFb0029607"},{"key":"47_CR3","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai, L. Hemachandra, and J. Vysko\u010d. Promise problems and access to unambiguous computation. In Proc. of 17th MFCS, number 629 in LNCS, pages 162\u2013171. Springer, 1992.","DOI":"10.1007\/3-540-55808-X_14"},{"issue":"2","key":"47_CR4","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S. Even","year":"1984","unstructured":"S. Even, A. Selman, and Y. Yacobi. The complexity of promise problems with applications to public-key cryptography. Inform. and Control, 61(2):159\u2013173, 1984.","journal-title":"Inform. and Control"},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"S. A. Fenner, L. J. Fortnow, and S. A. Kurtz. Gap-definable counting classes. In Proc. of 6th Conference on Structure in Complexity Theory, pages 30\u201342, 1991.","DOI":"10.1109\/SCT.1991.160241"},{"key":"47_CR6","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0304-3975(86)90165-9","volume":"43","author":"L. Goldschlager","year":"1986","unstructured":"L. Goldschlager and I. Parberry. On the construction of parallel computers from various bases of boolean functions. Theoretical Comput. Sci., 43:43\u201358, 1986.","journal-title":"Theoretical Comput. Sci."},{"key":"47_CR7","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J. Grollmann","year":"1988","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM J. Comput., 17:309\u2013335, 1988.","journal-title":"SIAM J. Comput."},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"U. Hertrampf. Locally definable acceptance types\u2014the three valued case. In Proc. of LATIN'92, number 583 in LNCS, pages 262\u2013271. Springer, 1992.","DOI":"10.1007\/BFb0023834"},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"U. Hertrampf. Locally definable acceptance types for polynomial time machines. In Proc. of 9th STACS, number 577 in LNCS, pages 199\u2013207. Springer, 1992.","DOI":"10.1007\/3-540-55210-3_184"},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"K.-J. Lange. Unambiguity of circuits. In Proc. of 5th Conference on Structure in Complexity Theory, pages 130\u2013137, 1990. (to appear in TCS).","DOI":"10.1109\/SCT.1990.113962"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"K.-J. Lange and P. Rossmanith. Characterizing unambiguous augmented pushdown automata by circuits. In Proc. of 15th MFCS, number 452 in LNCS, pages 399\u2013406. Springer, 1990.","DOI":"10.1007\/BFb0029635"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"R. Niedermeier and P. Rossmanith. Unambiguous simulations of auxiliary pushdown automata and circuits. In Proc. of LATIN'92, number 583 in LNCS, pages 387\u2013400. Springer, 1992.","DOI":"10.1007\/BFb0023843"},{"issue":"3","key":"47_CR13","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF01374525","volume":"25","author":"A. L. Selman","year":"1992","unstructured":"A. L. Selman. A survey of one-way functions in complexity theory. Mathematical Systems Theory, 25(3):203\u2013221, 1992.","journal-title":"Mathematical Systems Theory"},{"key":"47_CR14","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluating. Inform. Proc. Letters, 5:20\u201323, 1976.","journal-title":"Inform. Proc. Letters"},{"key":"47_CR15","unstructured":"K. W. Wagner. Alternating machines using partially defined \u201cAND\u201d and \u201cOR\u201d. Technical Report 39, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, Jan. 1992."}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:49:21Z","timestamp":1742593761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_47"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"27 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}