Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T08:08:30.044Z Has data issue: false hasContentIssue false
  • English
  • Français

On naturally continuous non-dcpo domains

Published online by Cambridge University Press:  22 June 2016

VLADIMIR SAZONOV
VLADIMIR SAZONOV*
Affiliation:
Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, U.K. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

After works of Normann and the author on sequentiality (Normann 2006Mathematical Structures in Computer Science16 (2) 279–289; Normann and Sazonov 2012Annals of Pure and Applied Logic163 (5) 575–603; Sazonov 2007Logical Methods in Computer Science3 (3:7) 1–50), the necessity and possibility of a non-dcpo domain theory became evident. In this paper, the category of continuous dcpo domains is generalized to a category of ‘naturally’ continuous non-dcpo domains with ‘naturally’ continuous maps as arrows. A full subcategory of the latter, assuming a kind of bounded-completeness requirement of domains and presence of ⊥ in each, proves to be Cartesian closed and equivalent to a subclass of Ershov's general A-spaces (Ershov 1974Algebra and Logics12 (4) 369–416). This extends a non-dcpo generalization of Scott (algebraic) domains introduced and proved to be equivalent to Ershov's general f-spaces (Ershov 1972Algebra and Logic11 (4) 367–437) in Sazonov (2007 op. cit.; 2009 Annals of Pure and Applied Logic159 (3) 341–355).

The current approach to natural domains (v-domains) is different from f-spaces and A-spaces in that it has arisen in Sazonov (2007 op. cit.) in a different way from defining fully abstract models for some versions of the language PCF over Integers, whereas the Ershov's approach was not initially related with full abstraction, and non-dcpo version of f-spaces and A-spaces were originally considered in an abstract (mainly topological) style. In this paper devoted to naturally continuous natural domains (v-continuous v-domains), we also work in an abstract (mainly order-theoretic) style but with the hope to relate it in the future with the ideas of PCF over Reals by exploring and adapting the ideas in Escardó (1996Theoretical Computer Science162 (1) 79–115), Escardó et al. (2004Mathematical Structures in Computer Science, 14 (6), Cambridge University Press 803–814), Marcial-Romero and Escardó (2007Theoretical Computer Science379 (1-2) 120–141), Sazonov (2007 op. cit.).

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1521 - 1552
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S., Jagadeesan, R. and Malacaria, P. (2000). Full abstraction for PCF. Information and Computation 163 (2) 409–470.Google Scholar
Abramsky, S. and Jung, A. (1994). Domain theory. In: Abramsky, S., Gabbay, D. and Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, volume III, Oxford University Press, 1–168.Google Scholar
Aczel, P. (1977). An introduction to inductive definitions. In: Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics, volume 90, Elsevier Science Publishers B.V., North Holland, 739–782.Google Scholar
Amadio, R.M. and Curien, P.-L. (1998). Domains and Lambda Calculus, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press.CrossRefGoogle Scholar
Ershov, Yu.L. (1972). Computable functionals of finite types. Algebra and Logic 11 (4) 367–437. (The journal is translated in English.)Google Scholar
Ershov, Yu.L. (1974). A theory of A-spaces. Algebra and Logics 12 (4) 369–416. (The journal is translated in English.)Google Scholar
Escardó, M.H. (1996). PCF extended with real numbers. Theoretical Computer Science 162 (1) 79–115.Google Scholar
Escardó, M.H., Hofmann, M. and Streicher, Th. (2004). On the non-sequential nature of the interval-domain model of real-number computation. In: Mathematical Structures in Computer Science, 14 (6), Cambridge University Press, 803–814.CrossRefGoogle Scholar
Escardó, M.H. and Ho, W.K. (2009). Operational domain theory and topology of sequential programming languages. Information and Computation 207 (3) 411–437.CrossRefGoogle Scholar
Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M. and Scott, D.S. (2003). Continuous Lattices and Domains, Cambridge University Press.CrossRefGoogle Scholar
Hyland, J.M.E. and Ong, C.-H.L. (2000). On full abstraction for PCF: I, II, and III. Information and Computation 163 (2) 285–408.Google Scholar
Marcial-Romero, J.R. and Escardó, M.H. (2007). Semantics of a sequential language for exact real-number computation. Theoretical Computer Science 379 (1–2) 120–141.Google Scholar
Nickau, H. (1996). Hereditarily-Sequential Functionals: A Game-Theoretic Approach to Sequentiality, Ph.D. Thesis, Siegen University, Siegen.Google Scholar
Normann, D. (2006). On sequential functionals of type 3. Mathematical Structures in Computer Science 16 (2) 279–289.Google Scholar
Normann, D. and Sazonov, V.Yu. (2012). The extensional ordering of the sequential functionals. Annals of Pure and Applied Logic 163 (5) 575–603.CrossRefGoogle Scholar
Plotkin, G. (1977). LCF considered as a programming language. Theoretical Computer Science 5 (3) 223–255.Google Scholar
Sazonov, V.Yu. (1976a). Functionals computable in series and in parallel. Sibirskii Matematicheskii Zhurnal 17 (3) 648–672. The journal is translated in English as Siberian Mathematical Journal.Google Scholar
Sazonov, V.Yu. (1976b). Expressibility of functionals in D.Scott's LCF language. Algebra and Logic 15 (3) 308–330. (The journal is translated in English.).Google Scholar
Sazonov, V.Y. (1976c). On Semantics of the Applicative Algorithmic Languages, Ph.D. Thesis, Institute of Mathematics, Novosibirsk (in Russian).Google Scholar
Sazonov, V.Y. (2007). Inductive definition and domain theoretic properties of fully abstract models for PCF and PCF+ . Logical Methods in Computer Science 3 (3:7) 1–50. http://www.lmcs-online.org.Google Scholar
Sazonov, V. (2009). Natural non-dcpo domains and f-spaces. Annals of Pure and Applied Logic 159 (3) 341–355.Google Scholar
Wright, J.B., Wagner, E.G. and Thatcher, J.W. (1978). A uniform approach to inductive posets and inductive closure. Theoretical Computer Science 7 (1) 57–77.CrossRefGoogle Scholar