{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T12:30:44Z","timestamp":1648989044732},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1998,9]]},"abstract":"<jats:p> Systems of uniform recurrence equations were proposed by Karp et\u00a0al.<jats:sup>13<\/jats:sup> as a mean of automatically deriving programs for parallel architectures. Extensions of this formalism are used by many authors in systolic array synthesis. The computability of a system of recurrence equations is therefore of primary importance, and is considered as the first point to be examined when trying to implement an algorithm. This paper investigates the computability of recurrence equations and especially new results obtained in this area. We first recall the definitions of computability proposed by Karp et\u00a0al.,<jats:sup>13<\/jats:sup> Rao,<jats:sup>31<\/jats:sup> Joinnault<jats:sup>12<\/jats:sup> and Saouter et\u00a0al.<jats:sup>32<\/jats:sup> Then we correct and generalize those results. Finally, we give a new original proof for the undecidability of computability of non-uniform, non-conditional systems of recurrence equations. <\/jats:p>","DOI":"10.1142\/s0129054198000179","type":"journal-article","created":{"date-parts":[[2003,5,14]],"date-time":"2003-05-14T06:56:49Z","timestamp":1052895409000},"page":"249-275","source":"Crossref","is-referenced-by-count":0,"title":["NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS"],"prefix":"10.1142","volume":"09","author":[{"given":"HERVE LE","family":"VERGE","sequence":"first","affiliation":[{"name":"IRISA, Campus de Beaulieu, Av. du G\u00e9n\u00e9ral Leclerc, F-35042 Rennes C\u00e9dex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YANNICK","family":"SAOUTER","sequence":"additional","affiliation":[{"name":"IRIT, Universit\u00e9 Paul Sabatier, 118 route de Narbonne, 31062 Toulouse C\u00e9dex\u00a04, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_2","first-page":"92","author":"Backes W.","year":"1992","journal-title":"Proceedings of SPAA"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1145\/153724.153727"},{"key":"p_4","first-page":"49","author":"Conway J. H.","year":"1972","journal-title":"Proc. Number Theory Conference, pages"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/028.1\/9813"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1145\/321406.321418"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360251"},{"key":"p_19","first-page":"627","author":"Leiserson C. E.","year":"1983","journal-title":"Proc. Int'l Conf. on Computer Design, pages"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01225647"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675929"},{"key":"p_27","author":"Quinton P.","year":"1989","journal-title":"The Journal of VLSI Signal Processing"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01558666"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1109\/71.86106"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054198000179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:31:19Z","timestamp":1565177479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054198000179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,9]]}},"alternative-id":["10.1142\/S0129054198000179"],"URL":"https:\/\/doi.org\/10.1142\/s0129054198000179","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,9]]}}}