{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T07:46:26Z","timestamp":1759131986370},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2002,6]]},"abstract":"<jats:p> Dijkstra's famous thesis \"goto considered harmful\", which paved the way for structured programming, was formally substantiated by the result of B\u00f6hm and Jacopini on the Turing universality of the three well-known basic programming constructs. We argue for a similar ideal in parallel programming \u2014 \"send-receive considered harmful\" \u2014 i.e. abandoning explicit send-receive statements between processors and expressing programs using a restricted set of parallel constructs. We deal with recursive patterns of parallelism, represented formally as morphisms in a suitable calculus. <\/jats:p><jats:p> The aim of this paper is to study the expressive power of two morphisms \u2013 catamorphisms and anamorphisms. For a restricted program calculus based on these morphisms, we constructively prove two formal results, whose pragmatic message is: (1) A programming language based on catamorphisms is computationally equivalent to the class of primitive recursive functions; (2) A programming language based on both catamorphisms and anamorphisms is equivalent to the class of partial recursive functions and is therefore Turing-universal. We present a case study on numerical integration, demonstrating the expressive power of ana- and catamorphisms for parallel programming. <\/jats:p>","DOI":"10.1142\/s012962640200094x","type":"journal-article","created":{"date-parts":[[2002,10,28]],"date-time":"2002-10-28T11:43:09Z","timestamp":1035805389000},"page":"229-246","source":"Crossref","is-referenced-by-count":5,"title":["TURING UNIVERSALITY OF RECURSIVE PATTERNS FOR PARALLEL PROGRAMMING"],"prefix":"10.1142","volume":"12","author":[{"given":"J\u00d6RG","family":"FISCHER","sequence":"first","affiliation":[{"name":"Techische Universit\u00e4t Berlin,  Sekr. 5-6, Franklinstra\u00dfe 28\/29,  10587 Berlin, Germany"}]},{"given":"SERGEI","family":"GORLATCH","sequence":"additional","affiliation":[{"name":"Techische Universit\u00e4t Berlin,  Sekr. 5-6, Franklinstra\u00dfe 28\/29,  10587 Berlin, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(92)90169-G"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1145\/355592.365646"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1145\/362929.362947"},{"key":"p_11","first-page":"273","volume":"26","author":"Gibbons J.","year":"1998","journal-title":"MD. USA"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(97)00014-2"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211000"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1145\/232629.232637"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003500"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007904422322"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211391"},{"key":"p_24","first-page":"324","volume":"25","author":"Meijer E.","year":"1995","journal-title":"CA. USA"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012962640200094X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:33:55Z","timestamp":1565184835000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012962640200094X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2002,6]]}},"alternative-id":["10.1142\/S012962640200094X"],"URL":"https:\/\/doi.org\/10.1142\/s012962640200094x","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}