{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:23:02Z","timestamp":1725664982444},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631651"},{"type":"electronic","value":"9783540691945"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63165-8_234","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:12:13Z","timestamp":1330297933000},"page":"816-826","source":"Crossref","is-referenced-by-count":4,"title":["Molecular computing, bounded nondeterminism, and efficient recursion"],"prefix":"10.1007","author":[{"given":"Richard","family":"Beigel","sequence":"first","affiliation":[]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"76_CR1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"L. Adleman","year":"1994","unstructured":"L. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021\u20131024, Nov. 1994.","journal-title":"Science"},{"key":"76_CR2","doi-asserted-by":"crossref","unstructured":"L. Adleman. On constructing a molecular computer. In 1st DIMACS workshop on DNA Computing, 1995.","DOI":"10.1090\/dimacs\/027\/01"},{"key":"76_CR3","doi-asserted-by":"crossref","unstructured":"E. Bach, A. Condon, E. Glaser, and C. Tanguay. DNA models and algorithms for NP-complete problems. In Proc. 11th Ann. Conf. Structure in Complexity Theory, pp. 290\u2013299, 1996.","DOI":"10.1109\/CCC.1996.507691"},{"key":"76_CR4","unstructured":"D. Beaver. A universal molecular computer. CSE 95-001, Penn. State Univ., 1995."},{"key":"76_CR5","unstructured":"R. Beigel. Maximum independent set algorithms. Manuscript, 1996."},{"key":"76_CR6","unstructured":"R. Beigel and D. Eppstein. 3-coloring in time O(1.3446n): a no-MIS algorithm. In Proc. 36th IEEE FOCS, pp. 444\u2013452, 1995."},{"key":"76_CR7","doi-asserted-by":"crossref","unstructured":"R. Beigel and J. Goldsmith. Downward separation fails catastrophically for limited nondeterminism classes. In Proc. 9th Ann. Conf. Structure in Complexity Theory, pp. 134\u2013138, 1994.","DOI":"10.1109\/SCT.1994.315810"},{"key":"76_CR8","doi-asserted-by":"crossref","unstructured":"D. Boneh, C. Dunworth, R. J. Lipton, and J. Sgall. On the computational power of DNA. Manuscript, 1996.","DOI":"10.1016\/S0166-218X(96)00058-3"},{"key":"76_CR9","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J. F. Buss","year":"1993","unstructured":"J. F. Buss and J. Goldsmith. Nondeterminism within P. SICOMP, 22:560\u2013572, 1993.","journal-title":"Nondeterminism within P. SICOMP"},{"key":"76_CR10","doi-asserted-by":"crossref","unstructured":"J. D. C. \u00c0lvarez and J. Tor\u00e1n. Complexity classes with complete problems between P and NP-complete. In Foundations of Computation Theory, pp. 13\u201324. Springer-Verlag, 1989. LNCS 380.","DOI":"10.1007\/3-540-51498-8_2"},{"key":"76_CR11","first-page":"21","volume":"23","author":"J. D\u00edaz","year":"1990","unstructured":"J. D\u00edaz and J. Tor\u00e1n. Classes of bounded nondeterminism. MST, 23:21\u201332, 1990.","journal-title":"MST"},{"key":"76_CR12","doi-asserted-by":"crossref","unstructured":"J. Goldsmith, M. Levy, and M. Mundhenk. Limited nondeterminism. SIGACT News, pp. 20\u201329, June 1996.","DOI":"10.1145\/235767.235769"},{"key":"76_CR13","doi-asserted-by":"crossref","unstructured":"L. Hemachandra and S. Jha. Defying upward and downward separation. In Proc. 10th STACS, pp. 185\u2013195. Springer-Verlag, 1993. LNCS 665.","DOI":"10.1007\/3-540-56503-5_21"},{"key":"76_CR14","volume-title":"PhD thesis","author":"C. M. R. Kintala","year":"1977","unstructured":"C. M. R. Kintala. Computations with a restricted number of nondeterministic steps. PhD thesis, Penn. State Univ., University Park, PA, 1977."},{"key":"76_CR15","doi-asserted-by":"crossref","unstructured":"C. M. R. Kintala and P. C. Fischer. Computations with a restricted number of nondeterministic steps. In Proc. 9th A CM STOC, pp. 178\u2013185, 1977.","DOI":"10.1145\/800105.803407"},{"issue":"1","key":"76_CR16","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C. M. R. Kintala","year":"1980","unstructured":"C. M. R. Kintala and P. C. Fischer. Refining nondeterminism in relativized polynomial-time bounded computations. SICOMP, 9(1):46\u201353, Feb. 1980.","journal-title":"SICOMP"},{"key":"76_CR17","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1126\/science.7725098","volume":"268","author":"R. Lipton","year":"1995","unstructured":"R. Lipton. Using DNA to solve NP-complete problems. Science, 268:542\u2013545, Apr. 1995.","journal-title":"Science"},{"key":"76_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"B. Monien and E. Speckenmeyer. Solving satisfiability in less than 2n steps. Discrete Appl. Math., 10:287\u2013295, 1985.","journal-title":"Discrete Appl. Math."},{"key":"76_CR19","unstructured":"M. Ogihara. Breadth first search 3SAT algorithms for DNA computers. TR 629, U. Rochester, July 1996."},{"key":"76_CR20","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. In Proc. 8th Ann. Conf. Structure in Complexity Theory, pp. 12\u201318, 1993.","DOI":"10.1109\/SCT.1993.336545"},{"key":"76_CR21","doi-asserted-by":"crossref","unstructured":"N. Pippenger and M. Fischer. Relations among complexity measures. J. ACM, 26, 1979.","DOI":"10.1145\/322123.322138"},{"key":"76_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J. Robson","year":"1986","unstructured":"J. Robson. Algorithms for maximum independent sets. J. Algorithms, 7:425\u2013440, 1986.","journal-title":"J. Algorithms"},{"key":"76_CR23","unstructured":"D. Roos and K. Wagner. On the power of bio-computers. TR, U. of Wurzburg, Feb. 1995. ftp:\/\/haegar.informatik.uni-wuerzburg.de\/pub\/TRs\/ro-wa95.ps.gz."},{"key":"76_CR24","unstructured":"P. Rothemund. A DNA and restriction enzyme implementation of Turing machines. http:\/\/www.ugcs.caltech.edu\/tt\u223cpwkr\/oett.html."},{"issue":"2","key":"76_CR25","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1142\/S0129054194000116","volume":"5","author":"L. Sanchis","year":"1994","unstructured":"L. Sanchis. Constructing language instances based on partial information. International Jour. Found. Comp. Sci., 5(2):209\u2013229, 1994.","journal-title":"International Jour. Found. Comp. Sci."},{"key":"76_CR26","unstructured":"I. Schiermeyer. Pure literal lookahead: An O(l,497n) 3-satisfiability algorithm. Manuscript, August 14, 1996."},{"key":"76_CR27","unstructured":"C. P. Schnorr. Optimal algorithms for self-reducible problems. In Proc. 3rd ICALP, pp. 322\u2013337, 1976."},{"key":"76_CR28","unstructured":"A. L. Selman. Natural self-reducible sets. TR, Northeastern Univ., 1986."},{"key":"76_CR29","doi-asserted-by":"crossref","unstructured":"W. Smith and A. Schweitzer. DNA computers in vitro and vivo. TR, NEC, 1995.","DOI":"10.1090\/dimacs\/027\/07"},{"key":"76_CR30","unstructured":"R. Tarjan. Finding a maximum clique. TR 72-123, Cornell Univ., 1972."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63165-8_234.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:16:35Z","timestamp":1605647795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63165-8_234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631651","9783540691945"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-63165-8_234","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}