Department of Computer Science and Technology

Technical reports

Using information systems to solve recursive domain equations effectively

Glynn Winskel, Kim Guldstrand Larsen

July 1984, 41 pages

Abstract

This paper aims to make two main contributions. One is to show how to use the concrete nature of Scott’s information systems to advantage in solving recursive domain equations. The method is based on the substructure relation between information systems. This essentially makes a complete partial order (cpo) of information systems. Standard domain constructions like function space can be made continuous on this cpo so the solution of recursive domain equations reduces to the more familiar construction of forming the least-fixed point of a continuous function. The second contribution again relies on the concrete nature of information systems, this time to develop a basic theory of effectively given information systems and through this present a simple treatment of effectively given domains.

Full text

PDF (2.9 MB)

BibTeX record

@TechReport{UCAM-CL-TR-51,
  author =	 {Winskel, Glynn and Larsen, Kim Guldstrand},
  title = 	 {{Using information systems to solve recursive domain
         	   equations effectively}},
  year = 	 1984,
  month = 	 jul,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-51.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-51}
}