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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
