{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T05:02:02Z","timestamp":1780030922778,"version":"3.53.1"},"reference-count":19,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022TS4Y3N"],"award-info":[{"award-number":["2022TS4Y3N"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100024370","name":"Government of Italy Ministry of Education University and Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100024370","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019771","name":"European Union's Research and Innovation","doi-asserted-by":"publisher","award":["CN00000013"],"award-info":[{"award-number":["CN00000013"]}],"id":[{"id":"10.13039\/100019771","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1016\/j.ipl.2026.106639","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T08:01:55Z","timestamp":1774512115000},"page":"106639","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A universal bound on the space complexity of directed acyclic graph computations"],"prefix":"10.1016","volume":"194","author":[{"given":"Gianfranco","family":"Bilardi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9569-2086","authenticated-orcid":false,"given":"Lorenzo","family":"De Stefani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ipl.2026.106639_bib0001","series-title":"Algorithmic procedures, generalized turing algorithms, and elementary recursion theory, in studies in logic and the Foundations of Mathematics","first-page":"361","volume":"61","author":"Friedman","year":"1971"},{"key":"10.1016\/j.ipl.2026.106639_bib0002","series-title":"Comparative Schematology, in Record of the Project MAC Conference on Concurrent Systems and Parallel Computation","first-page":"119","author":"Paterson","year":"1970"},{"key":"10.1016\/j.ipl.2026.106639_bib0003","series-title":"Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC)","first-page":"326","article-title":"I\/o complexity: the red-Blue pebble game","author":"Hong","year":"1981"},{"key":"10.1016\/j.ipl.2026.106639_bib0004","series-title":"Proceedings of the Sixth Annual ACM Symposium on Theory of Computing (STOC)","first-page":"33","article-title":"Storage requirements for deterministic\/polynomial time recognizable languages","author":"Cook","year":"1974"},{"key":"10.1016\/j.ipl.2026.106639_bib0005","series-title":"Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC)","article-title":"Speedups of deterministic machines by synchronous parallel machines","author":"Dymond","year":"1983"},{"key":"10.1016\/j.ipl.2026.106639_bib0006","series-title":"Graph-Theoretic Concepts in Computer Science","first-page":"47","article-title":"On the space and access complexity of computation DAGs","author":"Bilardi","year":"2000"},{"key":"10.1016\/j.ipl.2026.106639_bib0007","series-title":"Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","article-title":"The DAG visit approach for pebbling and i\/o lower bounds","author":"Bilardi","year":"2022"},{"issue":"2","key":"10.1016\/j.ipl.2026.106639_bib0008","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","article-title":"On time versus space","volume":"24","author":"Hopcroft","year":"1977","journal-title":"J. ACM"},{"key":"10.1016\/j.ipl.2026.106639_bib0009","series-title":"Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing (STOC)","first-page":"262","article-title":"Upper and lower bounds on time-Space tradeoffs","author":"Lengauer","year":"1979"},{"key":"10.1016\/j.ipl.2026.106639_bib0010","series-title":"Technical Report","article-title":"Minimum Register Allocation Is Complete in Polynomial Space","author":"Loui","year":"1979"},{"issue":"1","key":"10.1016\/j.ipl.2026.106639_bib0011","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","article-title":"Space bounds for a game on graphs","volume":"10","author":"Paul","year":"1976","journal-title":"Math. Syst. Theory"},{"issue":"7553","key":"10.1016\/j.ipl.2026.106639_bib0012","first-page":"436","volume":"521","author":"Lecun","year":"2015","journal-title":"Deep Learn. Nature"},{"key":"10.1016\/j.ipl.2026.106639_bib0013","first-page":"1929","article-title":"Dropout: a simple way to prevent neural networks from overfitting","volume":"15","author":"Srivastava","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"10.1016\/j.ipl.2026.106639_bib0014","series-title":"18Th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1977)","first-page":"162","article-title":"Applications of a planar separator theorem","author":"Lipton","year":"1977"},{"issue":"5","key":"10.1016\/j.ipl.2026.106639_bib0015","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/TIT.1978.1055938","article-title":"Space-Time tradeoffs on the FFT algorithm","volume":"24","author":"Savage","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.ipl.2026.106639_bib0016","series-title":"Models of Computation: Exploring the Power of Computing","author":"Savage","year":"1997"},{"key":"10.1016\/j.ipl.2026.106639_bib0017","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","article-title":"A separator theorem for planar graphs","volume":"36","author":"Lipton","year":"1977","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/j.ipl.2026.106639_bib0018","series-title":"Technical Report","article-title":"A Separator Theorem for Graphs of Bounded Genus","author":"Gilbert","year":"1982"},{"key":"10.1016\/j.ipl.2026.106639_bib0019","series-title":"Dynamic Generators of Topologically Embedded Graphs","author":"Eppstein","year":"2002"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000207?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000207?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T04:10:41Z","timestamp":1780027841000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019026000207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":19,"alternative-id":["S0020019026000207"],"URL":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106639","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A universal bound on the space complexity of directed acyclic graph computations","name":"articletitle","label":"Article Title"},{"value":"Information Processing Letters","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106639","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"106639"}}