{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:07:28Z","timestamp":1725570448856},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175169"},{"type":"electronic","value":"9783642175176"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17517-6_26","type":"book-chapter","created":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T20:13:41Z","timestamp":1291407221000},"page":"279-290","source":"Crossref","is-referenced-by-count":5,"title":["Fractal Parallelism: Solving SAT in Bounded Space and Time"],"prefix":"10.1007","author":[{"given":"Denys","family":"Duchier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Durand-Lose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxime","family":"Senot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/3-540-60692-0_68","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"E. Asarin","year":"1995","unstructured":"Asarin, E., Maler, O.: Achilles and the Tortoise climbing up the arithmetical hierarchy. In: Thiagarajan, P.S. (ed.) FSTTCS 1995. LNCS, vol.\u00a01026, pp. 471\u2013483. Springer, Heidelberg (1995)"},{"key":"26_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/3-540-63165-8_172","volume-title":"Automata, Languages and Programming","author":"O. Bournez","year":"1997","unstructured":"Bournez, O.: Some bounds on the computational power of piecewise constant derivative systems. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 143\u2013153. Springer, Heidelberg (1997)"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1023\/A:1025967225931","volume":"16","author":"T.A. Brun","year":"2003","unstructured":"Brun, T.A.: Computers with closed timelike curves can solve hard problems efficiently. Foundations of Physics Letters\u00a016, 245\u2013253 (2003)","journal-title":"Foundations of Physics Letters"},{"key":"26_CR4","first-page":"151","volume-title":"3rd Symposium on Theory of Computing (STOC 1971)","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: 3rd Symposium on Theory of Computing (STOC 1971), pp. 151\u2013158. ACM, New York (1971)"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Duchier, D., Durand-Lose, J., Senot, M.: Fractal parallelism: solving SAT in bounded space and time (extended version). Research Report RR-2010-08, LIFO, Universit\u00e9 d\u2019Orl\u00e9ans (2010), http:\/\/www.univ-orleans.fr\/lifo\/rapports.php","DOI":"10.1007\/978-3-642-17517-6_26"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/11494645_14","volume-title":"New Computational Paradigms","author":"J. Durand-Lose","year":"2005","unstructured":"Durand-Lose, J.: Abstract geometrical computation: Turing computing ability and undecidability. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol.\u00a03526, pp. 106\u2013116. Springer, Heidelberg (2005)"},{"key":"26_CR7","unstructured":"Durand-Lose, J.: Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model. In: Beckmann, A., Dimitracopoulos, C., L\u00f6we, B. (eds.) Logic and Theory of Algorithms, 4th Conf. Computability in Europe (CiE 2008) (abstracts and extended abstracts of unpublished papers), pp. 107\u2013116. University of Athens (2008)"},{"issue":"3","key":"26_CR8","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s11047-009-9117-0","volume":"8","author":"J. Durand-Lose","year":"2009","unstructured":"Durand-Lose, J.: Abstract geometrical computation\u00a03: Black holes for classical and analog computing. Nat. Comput.\u00a08(3), 455\u2013572 (2009a)","journal-title":"Nat. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Durand-Lose, J.: Abstract geometrical computation and computable analysis. In: Costa, J.F., Dershowitz, N. (eds.) UC 2009. LNCS, vol.\u00a05715, pp. 158\u2013167. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-03745-0_20"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1023\/A:1014019225365","volume":"41","author":"G. Etesi","year":"2002","unstructured":"Etesi, G., N\u00e9meti, I.: Non-turing computations via Malament-Hogarth space-time. International Journal of Theoret. Physics\u00a041, 341\u2013370 (2002)","journal-title":"International Journal of Theoret. Physics"},{"issue":"1","key":"26_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(89)90120-5","volume":"68","author":"U. Huckenbeck","year":"1989","unstructured":"Huckenbeck, U.: Euclidian geometry in terms of automata theory. Theoret. Comp. Sci.\u00a068(1), 71\u201387 (1989)","journal-title":"Theoret. Comp. Sci."},{"issue":"1","key":"26_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(90)90160-J","volume":"73","author":"G. Jacopini","year":"1990","unstructured":"Jacopini, G., Sontacchi, G.: Reversible parallel computation: an evolving space-model. Theoret. Comp. Sci.\u00a073(1), 1\u201346 (1990)","journal-title":"Theoret. Comp. Sci."},{"key":"26_CR13","unstructured":"Levin, L.: Universal search problems. In: Problems of Information Transmission, pp. 265\u2013266 (1973)"},{"issue":"1-2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(99)00328-X","volume":"259","author":"M. Margenstern","year":"2001","unstructured":"Margenstern, M., Morita, K.: NP problems are tractable in the space of cellular automata in the hyperbolic plane. Theor. Comp. Sci.\u00a0259(1-2), 99\u2013128 (2001)","journal-title":"Theor. Comp. Sci."},{"key":"26_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-45132-3_20","volume-title":"Machines, Computations, and Universality","author":"T.J. Naughton","year":"2001","unstructured":"Naughton, T.J., Woods, D.: On the computational power of a continuous-space optical model of computation. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol.\u00a02055, pp. 288\u2013299. Springer, Heidelberg (2001)"},{"issue":"1","key":"26_CR16","first-page":"75","volume":"6","author":"G. P\u0103un","year":"2001","unstructured":"P\u0103un, G.: P systems with active membranes: Attacking NP-Complete problems. Journal of Automata, Languages and Combinatorics\u00a06(1), 75\u201390 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"26_CR17","first-page":"305","volume-title":"Brainstorming Week on Membrane Computing","author":"P. Sos\u00edk","year":"2003","unstructured":"Sos\u00edk, P.: Solving a PSPACE-Complete problem by P-systems with active membranes. In: Cavaliere, M., Mart\u00edn-Vide, C., P\u0103un, G. (eds.) Brainstorming Week on Membrane Computing, pp. 305\u2013312. Universidad Rovira i Virgili, Tarragona (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17517-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T19:49:24Z","timestamp":1559850564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17517-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175169","9783642175176"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17517-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}