This paper presents an equivalence result between computability in the BSS model and in a suitable distributive category. It is proved that the class of functions Rm→Rn (with n,m finite and R a commutative, ordered ring) computable in the BSS model, and the functions distributively computable over a natural distributive graph based on the operations of R coincide. Using this result, a new structural characterization, based on iteration, of the same functions is given.
On the relations between distributive computability and the BSS model / S. Vigna. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 162:1(1996), pp. 5-21.
On the relations between distributive computability and the BSS model
S. VignaPrimo
1996
Abstract
This paper presents an equivalence result between computability in the BSS model and in a suitable distributive category. It is proved that the class of functions Rm→Rn (with n,m finite and R a commutative, ordered ring) computable in the BSS model, and the functions distributively computable over a natural distributive graph based on the operations of R coincide. Using this result, a new structural characterization, based on iteration, of the same functions is given.
Pubblicazioni consigliate
I metadati presenti in AIR sono rilasciati con licenza CCO mentre i file delle pubblicazioni sono rilasciati con licenza CC BY-SA, salvo diversa indicazione. In caso di violazione di copyright, contattare l'assistenza di AIR
