{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:28:13Z","timestamp":1772119693433,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,16]],"date-time":"2024-06-16T00:00:00Z","timestamp":1718496000000},"content-version":"vor","delay-in-days":15,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007837","name":"Universit\u00e4t Bremen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this paper, we continue the investigation of graph-based reaction systems. We extend the notion by input and output states as well as admitted context sequences to model explicitly input\u2013output relations and decision problems on the inputs. Moreover, we combine extended graph-based reaction systems into families to cover infinite input\u2013output relations and decision problems on infinite sets of graphs. This is used to model NP-problems on graphs and reductions between them as well as to prove their correctness.<\/jats:p>","DOI":"10.1007\/s11047-024-09984-3","type":"journal-article","created":{"date-parts":[[2024,6,16]],"date-time":"2024-06-16T05:01:44Z","timestamp":1718514104000},"page":"309-322","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Modeling NP-problems with families of extended graph-based reaction systems"],"prefix":"10.1007","volume":"23","author":[{"given":"Hans-J\u00f6rg","family":"Kreowski","sequence":"first","affiliation":[]},{"given":"Aaron","family":"Lye","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,16]]},"reference":[{"key":"9984_CR1","doi-asserted-by":"publisher","unstructured":"Brijder R, Ehrenfeucht A, Main MG, Rozenberg G (2011) A tour of reaction systems. Int J Found Comput Sci 22(7):1499\u20131517. https:\/\/doi.org\/10.1007\/3-540-65306-6_14","DOI":"10.1007\/3-540-65306-6_14"},{"key":"9984_CR2","unstructured":"Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fund Inform 75(1\u20134):263\u2013280"},{"issue":"1","key":"9984_CR3","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1142\/S0129054111007927","volume":"22","author":"A Ehrenfeucht","year":"2011","unstructured":"Ehrenfeucht A, Main MG, Rozenberg G (2011) Functions defined by reaction systems. Int J Found Comput Sci 22(1):167\u2013178","journal-title":"Int J Found Comput Sci"},{"key":"9984_CR4","doi-asserted-by":"publisher","unstructured":"Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G (2017) Evolving reaction systems. Theor Comput Sci 682:79\u201399. https:\/\/doi.org\/10.1016\/j.tcs.2016.12.031","DOI":"10.1016\/j.tcs.2016.12.031"},{"key":"9984_CR5","doi-asserted-by":"publisher","unstructured":"Ehrenfeucht A, Petre I, Rozenberg G (2017) Reaction systems: a model of computation inspired by the functioning of the living cell. In: Konstantinidis S, Moreira N, Reis R, Shallit J (eds) The role of theory in computing. World Scientific Publishing Co., Singapore, pp 11\u201332. https:\/\/doi.org\/10.1142\/9789813148208_000","DOI":"10.1142\/9789813148208_000"},{"key":"9984_CR6","doi-asserted-by":"publisher","unstructured":"Kreowski H-J, Kuske S, Lye A, Windhorst A (2022) A graph-transformational approach for proving the correctness of reductions between np-problems. In: Proceedings 13th international workshop on graph computation models, (GCM 2020). Electronic proceedings in theoretical computer science (EPTCS) vol. 330, pp. 71\u201387. Open Publishing Association, Waterloo. https:\/\/doi.org\/10.4204\/EPTCS.330.5","DOI":"10.4204\/EPTCS.330.5"},{"key":"9984_CR7","doi-asserted-by":"publisher","unstructured":"Kreowski H-J, Lye A (2020) Graph surfing in reaction systems from a categorial perspective. In: Hoffmann B, Minas M (eds.), Proc. 11th International workshop on graph computation models, (GCM 2020). Electronic proceedings in theoretical computer science (EPTCS), vol. 330, pp. 71\u201387. Open Publishing Association, Waterloo. https:\/\/doi.org\/10.4204\/EPTCS.330.5","DOI":"10.4204\/EPTCS.330.5"},{"key":"9984_CR8","doi-asserted-by":"publisher","unstructured":"Kreowski H-J, Lye A (2020) A categorial approach to reaction systems: first steps. Theor Comput Sci. https:\/\/doi.org\/10.1016\/j.tcs.2020.08.013","DOI":"10.1016\/j.tcs.2020.08.013"},{"key":"9984_CR9","doi-asserted-by":"publisher","unstructured":"Kreowski H-J, Rozenberg G (2019) Graph transformation through graph surfing in reaction systems. J Log Algebr Methods Programm. https:\/\/doi.org\/10.1016\/j.jlamp.2019.100481","DOI":"10.1016\/j.jlamp.2019.100481"},{"key":"9984_CR10","doi-asserted-by":"publisher","unstructured":"Kreowski H-J, Rozenberg G (2018) Graph surfing by reaction systems. In: Lambers L, Weber JH (eds.) 11th International Conference on Graph Transformation, ICGT 2018, Proceedings. Lecture Notes in Computer Science, vol. 10887, pp. 45\u201362. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-92991-0_4","DOI":"10.1007\/978-3-319-92991-0_4"},{"key":"9984_CR11","doi-asserted-by":"crossref","unstructured":"Lye A (2021) Transformations of reaction systems over categories by means of epi-mono factorization and functors. In: Gadducci F, Kehrer T (eds.), Graph Transformation: 14th International Conference, ICGT 2021, Held as Part of STAF 2021, Virtual Event, June 24\u201325, 2021, Proceedings. Lecture Notes in Computer Science, vol 12741. Springer, Cham, pp 40\u201359","DOI":"10.1007\/978-3-030-78946-6_3"},{"key":"9984_CR12","doi-asserted-by":"publisher","unstructured":"Nobile MS, Porreca AE, Spolaor S, Manzoni L, Cazzaniga P, Mauri G, Besozzi D (2017) Efficient simulation of reaction systems on graphics processing units. Fundam. Inform. 154(1\u20134):307\u2013321. https:\/\/doi.org\/10.3233\/FI-2017-1568","DOI":"10.3233\/FI-2017-1568"},{"key":"9984_CR13","doi-asserted-by":"publisher","unstructured":"Salomaa A (2012) Functions and sequences generated by reaction systems. Theoret Comput Sci 466(4\u20135):87\u201396. https:\/\/doi.org\/10.1016\/j.tcs.2012.07.022","DOI":"10.1016\/j.tcs.2012.07.022"},{"key":"9984_CR14","doi-asserted-by":"publisher","unstructured":"Turing AM (1936) On computable numbers, with an application to the entscheidungsproblem. In: Proceedings of the London Mathematical Society 2(42):230\u2013265. https:\/\/doi.org\/10.1112\/plms\/s2-42.1.230. A correction was published in Proceedings of the London Mathematical Society. 2 (1937). 43 (6): 544-6","DOI":"10.1112\/plms\/s2-42.1.230"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09984-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-024-09984-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09984-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T15:08:46Z","timestamp":1722611326000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-024-09984-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9984"],"URL":"https:\/\/doi.org\/10.1007\/s11047-024-09984-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3614234\/v1","asserted-by":"object"}]},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"5 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declares that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}