Normal forms, linearity, and prime algebraicity over nonflat domains

Karadais, Basil A. (2018): Normal forms, linearity, and prime algebraicity over nonflat domains. In: Mathematical Logic Quarterly, Bd. 64, Nr. 1-2: S. 55-88

Abstract

Using representations of nonflat Scott domains to model type systems, it is natural to wish that they be "linear", in which case the complexity of the fundamental test for entailment of information drops from exponential to linear, the corresponding mathematical theory becomes much simpler, and moreover has ties to models of computation arising in the study of sequentiality, concurrency, and linear logic. Earlier attempts to develop a fully nonflat semantics based on linear domain representations for a rich enough type system allowing inductive types, were designed in a way that felt rather artificial, as it featured certain awkward and counter-intuitive properties;eventually, the focus turned on general, nonlinear representations. Here we try to turn this situation around, by showing that we can work linearly in a systematic way within the nonlinear model, and that we may even restrict to a fully linear model whose objects are in a bijective correspondence with the ones of the nonlinear and are easily seen to form a prime algebraic domain. To obtain our results we study mappings of finite approximations of objects that can be used to turn approximations into normal and linear forms.

• Dokumententyp: Zeitschriftenartikel
• Fakultät: Mathematik, Informatik und Statistik > Mathematik
• Themengebiete: 500 Naturwissenschaften und Mathematik > 510 Mathematik
• ISSN: 0942-5616
• Sprache: Englisch