Given a poset $P$, the set, $\Gamma(P)$, of all Scott closed sets ordered by inclusion forms a complete lattice. A subcategory $\mathbf{C}$ of $\mathbf{Pos}_d$ (the category of posets and Scott-continuous maps) is said to be $\Gamma$-faithful if for any posets $P$ and $Q$ in $\mathbf{C}$, $\Gamma(P) \cong \Gamma(Q)$ implies $P \cong Q$. It is known that the category of all continuous dcpos and the category of bounded complete dcpos are $\Gamma$-faithful, while $\mathbf{Pos}_d$ is not. Ho & Zhao (2009) asked whether the category $\mathbf{DCPO}$ of dcpos is $\Gamma$-faithful. In this paper, we answer this question in the negative by exhibiting a counterexample. To achieve this, we introduce a new subcategory of dcpos which is $\Gamma$-faithful. This subcategory subsumes all currently known $\Gamma$-faithful subcategories. With this new concept in mind, we construct the desired counterexample which relies heavily on Johnstone's famous dcpo which is not sober in its Scott topology.

A general theory of presentations for d-frames does not yet exist. We review the difficulties and give sufficient conditions for when they can be overcome. As an application we prove that the category of d-frames is closed under coproducts.

We introduce a general diagrammatic theory of digital circuits, based on connections between monoidal categories and graph rewriting. The main achievement of the paper is conceptual, filling a foundational gap in reasoning syntactically and symbolically about a large class of digital circuits (discrete values, discrete delays, feedback). This complements the dominant approach to circuit modelling, which relies on simulation. The main advantage of our symbolic approach is the enabling of automated reasoning about parametrised circuits, with a potentially interesting new application to partial evaluation of digital circuits. Relative to the recent interest and activity in categorical and diagrammatic methods, our work makes several new contributions. The most important is establishing that categories of digital circuits are Cartesian and admit, in the presence of feedback expressive iteration axioms. The second is producing a general yet simple graph-rewrite framework for reasoning about such categories in which the rewrite rules are computationally efficient, opening the way for practical applications.

Este es el manuscrito aceptado del artículo. La versión registrada fue publicada por primera vez en Journal of Logic and Computation, 27, 2017, pp. 155-199, está disponible en línea en el sitio web del editor: https://doi.org/10.1093/logcom/exv038 This is the accepted manuscript of the article. The registered version was first published in Journal of Logic and Computation, 27, 2017, pp. 155-199, is available online at the publisher's website: https://doi.org/10.1093/logcom/exv038

This paper proposes a categorical theory of digital circuits based on monoidal categories and graph rewriting. The main goal of this paper is conceptual: to fill a foundational gap in reasoning about digital circuits, which is currently almost exclusively semantic (simulations). The level of abstraction we target is circuits with discrete signal levels, discrete time, and explicit delays, which is appropriate for modelling a range of components such as boolean gates or transistors working in saturation mode. We start with an algebraic signature consisting of the basic electronic components of a given class of circuits and extend it gradually (and in a free way) with further algebraic structure (representing circuit combinations, delays, and feedback), while quotienting it with a notion of equivalence corresponding to input-output observability. Using well-known results about the correspondence between free monoidal categories and graph-like structures we can develop, in a principled way, a graph rewriting system which is shown to be useful in reasoning about such circuits. We illustrate the power of our system by reasoning equationally about a challenging class of circuits: combinational circuits with feedback.

We employ the well-developed and powerful techniques of algebraic semantics and Priestley duality to set up a Kripke semantics for a modal expansion of Arieli and Avron's bilattice logic, itself based on Belnap's four-valued logic. We obtain soundness and completeness of a Hilbert-style derivation system for this logic with respect to four-valued Kripke frames, the standard notion of model in this setting. The proof is via intermediary relational structures which are analysed through a topological reading of one of the axioms of the logic. Both local and global consequence on the models are covered.

This special issue of Mathematical Structures in Computer Science contains six papers from the Workshop on Domains IX held at the University of Sussex (Brighton), on 22–24 September 2008. This was the ninth event in the long tradition of Domains workshops, which started in Darmstadt in 1994. Since then, workshops have been organised in Braunschweig (1996), Munich (1997), Siegen (1998), Darmstadt again (1999, 2004), Birmingham (2002) and Novosibirsk (2007).

This is the second part of a special issue in honour of Klaus Keimel – the first part appeared in Mathematical Structures in Computer Science16 (2). This second part consists of a single paper by John Longley, which could not be included in the earlier issue for reasons of size.

In late August 2004, some 60 mathematicians and computer scientists gathered in Darmstadt for the seventh Workshop Domains, to mark the 65th birthday of Professor Klaus Keimel and his retirement from his position at the Technical University Darmstadt. The papers in this volume were selected from submissions that were received in response to a call issued to participants during the meeting, and to a wider community afterwards.

Domain theory, which was introduced by Dana Scott in the early 1970s, works on the principle of incorporating partial elements into denotational domains. The resulting structures are ordered by a natural notion of refinement or approximation, and they carry a topology that expresses the process of passing to a limit.

We study a Gentzen style sequent calculus where the formulas on the left and right of the turnstile need not necessarily come from the same logical system. Such a sequent can be seen as a consequence between different domains of reasoning. We discuss the ingredients needed to set up the logic generalised in this fashion. The usual cut rule does not make sense for sequents which connect different logical systems because it mixes formulas from antecedent and succedent. We propose a different cut rule which addresses this problem. The new cut rule can be used as a basis for composition in a suitable category of logical systems. As it turns out, this category is equivalent to coherent spaces with certain relations between them. Finally, cut elimination in this set-up can be employed to provide a new explanation of the domain constructions in Samson Abramsky's Domain Theory in Logical Form.

We enrich the *-autonomous category of complete lattices and maps preserving all suprema with the important concept of approximation by specifying a *-autonomous full subcategory LFS of linear FS-lattices. This is the greatest *-autonomous full subcategory of linked bicontinuous lattices. The modalities !() and ?() mediate a duality between the upper and lower powerdomains. The distributive objects in LFS give rise to the compact closed *-autonomous full subcategory CD of completely distributive lattices. We characterise algebraic objects in LFS by forbidden substructures 'a la Plotkin'.>

Much of relational algebra and the underlying principles of relational database design have a simple representation in the theory of domains that is traditionally used in the denotational semantics of programming languages. By investigating the possible orderings on powerdomains that are well known in the study of nondeterminism and concurrency it is possible to show that many of the ideas in relational databases apply to structures that are much more general than relations. This also suggests a method of representing database objects as typed objects in programming languages. In this paper we show how operations such as natural join and projection—which are fundamental to relational database design—can be generalized, and we use this generalized framework to give characterizations of several relational database concepts including functional dependencies and universal relations. All of these have a simple-minded semantics in terms of the underlying domains, which can be thought of as domains of partial descriptions of “real-world” objects. We also discuss the applicability of relational database theory to nonrelational structures such as records with variants, higher-order relations, recursive structures and other ordered spaces.

The long-standing problem of finding the maximal Cartesian closed categories of continuous domains is solved. The solution requires the definition of a new class of continuous domains, called FS-domains, which contains all retracts of SFP-objects. The properties of FS-domains are discussed.>

Almost all of the categories normally used as a mathematical foundation for denotational semantics satisfy a condition known as consistent completeness. The authors explore the possibility of using different condition coherence, which has its origin in topology and logic. In particular, they concentrate on posets with principal ideas that are algebraic lattices and with coherent topologies. These form a Cartesian closed category which has fixed points for domain equations. It is shown that a universal domain exists. A categorical treatment of the construction of this domain is provided, and its relationship to other applications discussed.>