{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:05Z","timestamp":1753894385873,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T00:00:00Z","timestamp":1646265600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["648701"],"award-info":[{"award-number":["648701"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The concept of decomposition in computer science and engineering is\nconsidered a fundamental component of computational thinking and is prevalent\nin design of algorithms, software construction, hardware design, and more. We\npropose a simple and natural formalization of sequential decomposition, in\nwhich a task is decomposed into two sequential sub-tasks, with the first\nsub-task to be executed before the second sub-task is executed. These tasks are\nspecified by means of input\/output relations. We define and study decomposition\nproblems, which is to decide whether a given specification can be sequentially\ndecomposed. Our main result is that decomposition itself is a difficult\ncomputational problem. More specifically, we study decomposition problems in\nthree settings: where the input task is specified explicitly, by means of\nBoolean circuits, and by means of automatic relations. We show that in the\nfirst setting decomposition is NP-complete, in the second setting it is\nNEXPTIME-complete, and in the third setting there is evidence to suggest that\nit is undecidable. Our results indicate that the intuitive idea of\ndecomposition as a system-design approach requires further investigation. In\nparticular, we show that adding a human to the loop by asking for a\ndecomposition hint lowers the complexity of decomposition problems\nconsiderably.<\/jats:p>","DOI":"10.46298\/lmcs-18(1:37)2022","type":"journal-article","created":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T17:40:26Z","timestamp":1646329226000},"source":"Crossref","is-referenced-by-count":1,"title":["Sequential Relational Decomposition"],"prefix":"10.46298","volume":"Volume 18, Issue 1","author":[{"given":"Dror","family":"Fried","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Axel","family":"Legay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u00ebl","family":"Ouaknine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2022,3,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/9165\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/9165\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:17:17Z","timestamp":1687292237000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/5250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-18(1:37)2022","relation":{"has-preprint":[{"id-type":"arxiv","id":"1903.01368v4","asserted-by":"subject"},{"id-type":"arxiv","id":"1903.01368v3","asserted-by":"subject"},{"id-type":"arxiv","id":"1903.01368v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1903.01368v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1903.01368","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1903.01368","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2022,3,3]]},"article-number":"5250"}}