Domains via Graphs

This paper provides a concrete and simple introduction to two pillars ofdomain theory: (1) solving recursive domain equations, and (2) universaland saturated domains. Our exposition combines Larsen and Winskel's ideaon solving domain equations using information systems with Girard's ideaof stable domain theory in the form of coherence spaces, or graphs.Detailed constructions are given for universal and even homogeneousobjects in two categories of graphs: one representing binary complete,prime algebraic domains with complete primes covering the bottom; theother representing omega-algebraic, prime algebraic lattices. Theback-and-forth argument in model theory helps to enlighten theconstructions.