Admissible representations of effective cpo's

In theoretical computer science studies, the notion of an effective cpo (complete partial order) is a very useful tool, especially in works devoted to semantics (see, among others, the work of D. Scott, G. Plotkin, M. Smyth, H. Egli and R. Constable). A cpo is an abstract object in general. A concrete machine cannot operate with such an object but only with names of objects. The authors define admissible representations for effective cpo's via two axioms which generalize the axioms for Gödel numberings of the partial recursive functions. By typological and recursion-theoretic considerations, they show that this definition is quite natural and the link between representations of a cpo D and the admissible numberings of \(D_{re}\), the set of all recursively enumerable elements of D. This article is clear and well-written and provides insight for further study of a theory of computational complexity for cpo functions. It would be of interest in connection with the notion of computation, which plays a crucial role in theoretical computer science.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Admissible representations of effective cpo's

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068562)