{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T17:25:35Z","timestamp":1778520335879,"version":"3.51.4"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T00:00:00Z","timestamp":1684886400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T00:00:00Z","timestamp":1684886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K11896"],"award-info":[{"award-number":["19K11896"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Knuth\u2019s 0\u20131 principle argues that the correctness of any swap-based sorting network can be verified by testing arbitrary sequences over Boolean values (i.e., 0 and 1). Voigtl\u00e4nder (Proceedings of the 35th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2008, San Francisco, California, USA, January 7\u201312, 2008. ACM, New York, NY, pp 29\u201335, 2008. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1145\/1328438.1328445\">https:\/\/doi.org\/10.1145\/1328438.1328445<\/jats:ext-link>) proved a similar result for prefix-sum networks that consist of associative binary operators: the correctness can be verified by testing arbitrary sequences and associative binary operators over three values, namely 0, 1, and 2. He raised the question of whether testing over Boolean values is sufficient if the binary operator is idempotent in addition to associative. This paper answers his question. First, there is an incorrect prefix-sum network for associative idempotent operators, the flaw of which cannot be detected by testing over Boolean values. Second, testing over Boolean values is sufficient if the binary operators are restricted to commutative in addition to associative and idempotent.<\/jats:p>","DOI":"10.1007\/s00354-023-00219-0","type":"journal-article","created":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T08:02:27Z","timestamp":1684915347000},"page":"523-531","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["When does 0\u20131 Principle Hold for Prefix Sums?"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2741-5954","authenticated-orcid":false,"given":"Akimasa","family":"Morihata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,24]]},"reference":[{"key":"219_CR1","volume-title":"The Art of Computer Programming","author":"D Knuth","year":"1998","unstructured":"Knuth, D.: The Art of Computer Programming, vol. 3, 2nd edn. Addison Wesley Longman, Boston, MA, USA (1998)","edition":"2"},{"key":"219_CR2","volume-title":"Synthesis of Parallel Algorithms, Chap. 1","author":"GE Blelloch","year":"1993","unstructured":"Blelloch, G.E.: Prefix sums and their applications. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms, Chap. 1. Morgan Kaufmann Publishers, Burlington, MA, USA (1993)"},{"key":"219_CR3","doi-asserted-by":"publisher","unstructured":"Hinze, R.: An algebra of scans. In: Kozen, D., Shankland, C. (eds) Mathematics of Program Construction, 7th International Conference, MPC 2004, Stirling, Scotland, UK, July 12\u201314, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3125, pp. 186\u2013210. Springer, Berlin, Germany (2004). https:\/\/doi.org\/10.1007\/978-3-540-27764-4_11","DOI":"10.1007\/978-3-540-27764-4_11"},{"key":"219_CR4","doi-asserted-by":"publisher","unstructured":"Voigtl\u00e4nder, J.: Much ado about two (pearl): a pearl on parallel prefix computation. In: Necula, G.C., Wadler, P. (eds.) Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, January 7\u201312, 2008, pp. 29\u201335. ACM, New York, NY, USA (2008). https:\/\/doi.org\/10.1145\/1328438.1328445","DOI":"10.1145\/1328438.1328445"},{"issue":"1","key":"219_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1017\/S0956796810000304","volume":"21","author":"M Sheeran","year":"2011","unstructured":"Sheeran, M.: Functional and dynamic programming in the design of parallel prefix networks. J. Funct. Program. 21(1), 59\u2013114 (2011). https:\/\/doi.org\/10.1017\/S0956796810000304","journal-title":"J. Funct. Program."},{"key":"219_CR6","doi-asserted-by":"publisher","unstructured":"Chong, N., Donaldson, A.F., Ketema, J.: A sound and complete abstraction for reasoning about parallel prefix sums. In: Jagannathan, S., Sewell, P. (eds.) The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL \u201914, San Diego, CA, USA, January 20\u201321, 2014, pp. 397\u2013410. ACM, New York, NY, USA (2014). https:\/\/doi.org\/10.1145\/2535838.2535882","DOI":"10.1145\/2535838.2535882"},{"issue":"2","key":"219_CR7","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/s10766-016-0414-9","volume":"45","author":"K Matsuzaki","year":"2017","unstructured":"Matsuzaki, K.: Functional models of Hadoop MapReduce with application to scan. Int. J. Parallel Program. 45(2), 362\u2013381 (2017). https:\/\/doi.org\/10.1007\/s10766-016-0414-9","journal-title":"Int. J. Parallel Program."},{"key":"219_CR8","doi-asserted-by":"publisher","unstructured":"Safari, M., Oortwijn, W., Joosten, S.J.C., Huisman, M.: Formal verification of parallel prefix sum. In: Lee, R., Jha, S., Mavridou, A. (eds.) NASA Formal Methods\u201412th International Symposium, NFM 2020, Moffett Field, CA, USA, May 11\u201315, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12229, pp. 170\u2013186. Springer, Berlin, Germany (2020). https:\/\/doi.org\/10.1007\/978-3-030-55754-6_10","DOI":"10.1007\/978-3-030-55754-6_10"},{"key":"219_CR9","volume-title":"Haskell 98 Language and Libraries: The Revised Report","year":"2003","unstructured":"Peyton Jones, S. (ed.): Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, Cambridge, UK (2003)"},{"key":"219_CR10","doi-asserted-by":"publisher","unstructured":"Lynch, T.W. Jr., Swartzlander, E.: The redundant cell adder. In: 10th IEEE Symposium on Computer Arithmetic, ARITH 1991, Grenoble, France, June 26\u201328, 1991, pp. 165\u2013170. IEEE (1991). https:\/\/doi.org\/10.1109\/ARITH.1991.145553","DOI":"10.1109\/ARITH.1991.145553"},{"key":"219_CR11","doi-asserted-by":"publisher","unstructured":"Beaumont-Smith, A., Lim, C.: Parallel prefix adder design. In: 15th IEEE Symposium on Computer Arithmetic (Arith-15 2001), 11\u201317 June 2001, Vail, CO, USA, p. 218. IEEE (2001). https:\/\/doi.org\/10.1109\/ARITH.2001.930122","DOI":"10.1109\/ARITH.2001.930122"},{"key":"219_CR12","unstructured":"Day, N.A., Launchbury, J., Lewis, J.: Logical abstractions in Haskell. In: Proceedings of the 1999 Haskell Workshop. Utrecht University Department of Computer Science, Technical Report UU-CS-1999-28, Utrecht, Netherlands (1999)"},{"key":"219_CR13","first-page":"513","volume":"83","author":"JC Reynolds","year":"1983","unstructured":"Reynolds, J.C.: Types, abstraction and parametric polymorphism. Information Processing 83, 513\u2013523 (1983)","journal-title":"Information Processing"},{"key":"219_CR14","doi-asserted-by":"publisher","unstructured":"Wadler, P.: Theorems for free! In: FPCA\u201989 Conference on Functional Programming Languages and Computer Architecture. Imperial College, London, England, 11\u201313 September 1989, pp. 347\u2013359. ACM, New York (1989). https:\/\/doi.org\/10.1145\/99370.99404","DOI":"10.1145\/99370.99404"},{"key":"219_CR15","doi-asserted-by":"publisher","unstructured":"Bernardy, J., Jansson, P., Claessen, K.: Testing polymorphic properties. In: Gordon, A.D. (ed.) Programming Languages and Systems, 19th European Symposium on Programming, ESOP 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20\u201328, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6012, pp. 125\u2013144. Springer, Berlin, Germany (2010). https:\/\/doi.org\/10.1007\/978-3-642-11957-6_8","DOI":"10.1007\/978-3-642-11957-6_8"},{"key":"219_CR16","doi-asserted-by":"publisher","unstructured":"Hou, K., Wang, Z.: Logarithm and program testing. Proc. ACM Program. Lang. 6(POPL), 1\u201326 (2022). https:\/\/doi.org\/10.1145\/3498726","DOI":"10.1145\/3498726"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-023-00219-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00354-023-00219-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-023-00219-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T10:08:05Z","timestamp":1694858885000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00354-023-00219-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,24]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["219"],"URL":"https:\/\/doi.org\/10.1007\/s00354-023-00219-0","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,24]]},"assertion":[{"value":"30 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}