{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:24:29Z","timestamp":1740108269413,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T00:00:00Z","timestamp":1707177600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T00:00:00Z","timestamp":1707177600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Union, European Social Fund","award":["EFOP-3.6.3-VEKOP-16-2017-00002"],"award-info":[{"award-number":["EFOP-3.6.3-VEKOP-16-2017-00002"]}]},{"DOI":"10.13039\/501100009232","name":"University of Debrecen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009232","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we develop computing machinery within the framework of the String Multiset Rewriting calculus (SMSR), as defined by Barbuti et al. [4], to solve the SAT problem in linear time regarding the number of variables of a given conjunctive normal form. This shows that SMSR can be considered a computational model capable of significantly reducing the time requirement of classical decision problems.\n<\/jats:p>","DOI":"10.1007\/s00607-024-01258-1","type":"journal-article","created":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T17:39:28Z","timestamp":1707241168000},"page":"1321-1334","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving the SAT problem with the string multiset rewriting calculus"],"prefix":"10.1007","volume":"106","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6703-9661","authenticated-orcid":false,"given":"P\u00e9ter","family":"Batty\u00e1nyi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,6]]},"reference":[{"key":"1258_CR1","doi-asserted-by":"publisher","unstructured":"Alhazov A, Cojocaru S, Gheorghe M, Rogozhin Y, Rozenberg G, Salomaa A (eds.) (2014) Membrane Computing. CMC 2013. Lecture Notes in Computer Science, vol. 8340, Springer, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-54239-8_14","DOI":"10.1007\/978-3-642-54239-8_14"},{"key":"1258_CR2","doi-asserted-by":"publisher","unstructured":"Ausiello G, Karhum\u00e4ki J, Mauri G, Ong L (eds.) (2008) Fifth IFIP international conference on theoretical computer science-TCS 2008. IFIP International federation for information processing, Springer, vol. 273, Boston, MA. https:\/\/doi.org\/10.1007\/978-0-387-09680-3_18","DOI":"10.1007\/978-0-387-09680-3_18"},{"key":"1258_CR3","unstructured":"Bagossy A, Batty\u00e1nyi P, An encoding of the $$\\lambda$$-calculus in the String MultiSet Rewriting calculus, Acta Informatica (to appear)"},{"key":"1258_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.entcs.2007.12.004","volume":"194","author":"R Barbuti","year":"2008","unstructured":"Barbuti R, Caravagna G, Maggiolo-Schettini A, Milazzo P (2008) An intermediate language for the simulation of biological systems. Electron Notes Theoret Comput Sci 194:19\u201334","journal-title":"Electron Notes Theoret Comput Sci"},{"key":"1258_CR5","first-page":"21","volume":"72","author":"R Barbuti","year":"2006","unstructured":"Barbuti R, Maggiolo-Schettini A, Milazzo P, Troina A (2006) A calculus of looping sequences for modelling microbiological systems. Fund Inform 72:21\u201335","journal-title":"Fund Inform"},{"key":"1258_CR6","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1126\/science.1069528","volume":"296","author":"RS Braich","year":"2002","unstructured":"Braich RS, Chelyapov N, Johnson C, Rothemund PWK, Adleman L (2002) Solution of a 20-Variable 3-SAT problem on a DNA computer. Science 296:499\u2013502. https:\/\/doi.org\/10.1126\/science.1069528","journal-title":"Science"},{"key":"1258_CR7","doi-asserted-by":"crossref","unstructured":"Cardelli L, Brane Calculi. Interactions of biological membranes. In [10] 257\u2013280","DOI":"10.1007\/978-3-540-25974-9_24"},{"key":"1258_CR8","doi-asserted-by":"crossref","unstructured":"Cardelli L (2008) From processes to ODEs by Chemistry. In [2] 261\u2013281","DOI":"10.1007\/978-0-387-09680-3_18"},{"key":"1258_CR9","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.tcs.2004.03.065","volume":"325","author":"V Danos","year":"2004","unstructured":"Danos V, Laneve C (2004) Formal molecular biology. Theoret Comput Sci\u00a0325:69\u2013110","journal-title":"Theoret Comput Sci"},{"key":"1258_CR10","doi-asserted-by":"crossref","unstructured":"Danos V, Schachter V (eds.) (2005) 1CMSB\u201904: Proceedings of the 20 international conference on computational methods in systems biology. Lecture Notes in Computer Science, vol. 3082, Springer, Berlin","DOI":"10.1007\/b107287"},{"key":"1258_CR11","doi-asserted-by":"crossref","unstructured":"Gazdag Zs Solving SAT by P Systems with active membranes in linear time in the number of variables. In [1] 189\u2013205","DOI":"10.1007\/978-3-642-54239-8_14"},{"key":"1258_CR12","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2006.10.013","volume":"371","author":"MA Guti\u00e9rrez-Naranjo","year":"2007","unstructured":"Guti\u00e9rrez-Naranjo MA, P\u00e9rez-Jim\u00e9nez MJ, Romero-Campero FJ (2007) A uniform solution to SAT using membrane creation. Theoret Comput Sci 371:54\u201361","journal-title":"Theoret Comput Sci"},{"key":"1258_CR13","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1126\/science.7725098","volume":"268","author":"RJ Lipton","year":"1995","unstructured":"Lipton RJ (1995) Using DNA to solve NP-complete problems. Science 268:542\u2013545","journal-title":"Science"},{"key":"1258_CR14","doi-asserted-by":"crossref","unstructured":"Martinelli F, Bistarelli S, Cervesato I, Lenzini G, Marangoni R, Representing biological systems through multiset rewriting. In [15], 415\u2013426","DOI":"10.1007\/978-3-540-45210-2_38"},{"key":"1258_CR15","doi-asserted-by":"crossref","unstructured":"Moreno Diaz R, Pichler F (eds.) (2004) Computer aided systems theory (EUROCAST \u201903). Lecture Notes in Computer Science, vol. 2809, Springer","DOI":"10.1007\/11556985"},{"issue":"1","key":"1258_CR16","first-page":"75","volume":"6","author":"Gh P\u0103un","year":"1999","unstructured":"P\u0103un Gh (1999) P systems with active membranes: attacking NP complete problems. J Automata Lang Comb 6(1):75\u201390","journal-title":"J Automata Lang Comb"},{"issue":"1","key":"1258_CR17","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jcss.1999.1693","volume":"61","author":"Gh P\u0103un","year":"2000","unstructured":"P\u0103un Gh (2000) Computing with membranes. J Comput Syst Sci 61(1):108\u2013143","journal-title":"J Comput Syst Sci"},{"issue":"7","key":"1258_CR18","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1093\/comjnl\/38.7.578","volume":"38","author":"C Priami","year":"1995","unstructured":"Priami C (1995) Stochastic $$\\pi$$-Calculus.\u00a0Comput J 38(7):578\u2013589","journal-title":"Comput J"},{"key":"1258_CR19","doi-asserted-by":"publisher","unstructured":"Thachuk C, Liu Y (eds.) (2019) DNA computing and molecular programming. DNA 2019. Lecture Notes in Computer Science, vol. 11648, Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-26807-7_1","DOI":"10.1007\/978-3-030-26807-7_1"},{"key":"1258_CR20","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.entcs.2020.06.006","volume":"350","author":"M Troj\u00e1k","year":"2020","unstructured":"Troj\u00e1k M, \u0160afr\u00e1nek D, Brim L, \u0160nalagovi\u010d J, \u010cerven\u00fd J (2020) Executable biochemical space for specification and analysis of biochemical systems. Electron Notes Theoret Comput Sci 350:91\u2013116","journal-title":"Electron Notes Theor Comput Sci"},{"key":"1258_CR21","unstructured":"Troj\u00e1k M, Pastva S, \u0160afr\u00e1nek D, Brim L, Regulated multiset rewriting systems, arXiv:2111.13036"},{"key":"1258_CR22","doi-asserted-by":"publisher","first-page":"104843","DOI":"10.1016\/j.biosystems.2023.104843","volume":"225","author":"M Troj\u00e1k","year":"2023","unstructured":"Troj\u00e1k M, \u0160afr\u00e1nek D, Pastva S, Brim L (2023) Rule-based modelling of biological systems using regulated rewriting. Biosystems 225:104843. https:\/\/doi.org\/10.1016\/j.biosystems.2023.104843","journal-title":"Biosystems"},{"key":"1258_CR23","doi-asserted-by":"crossref","unstructured":"Winfree E. Chemical reaction networks and stochastic local search. In [19] 1\u201320","DOI":"10.1007\/978-3-030-26807-7_1"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-024-01258-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00607-024-01258-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00607-024-01258-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,20]],"date-time":"2024-05-20T18:03:55Z","timestamp":1716228235000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00607-024-01258-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,6]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1258"],"URL":"https:\/\/doi.org\/10.1007\/s00607-024-01258-1","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"type":"print","value":"0010-485X"},{"type":"electronic","value":"1436-5057"}],"subject":[],"published":{"date-parts":[[2024,2,6]]},"assertion":[{"value":"17 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares no conflict of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}