Some programs are not merely sets of batch instructions performed in isolation. They interact, either directly with the user, or with other threads and resources. This dissertation tackles the problem of mathematical description (denotational semantics) of the observable behaviour of such programs. In the tradition of denotational semantics and functional programming, one can distinguish between pure computations, which are regarded as mathematical functions, and effectful ones, like those generating behaviour. Both effects in general and behaviour of interactive systems have been thoroughly studied, and they both have elegant category-theoretic explanations: the frameworks of, respectively, monads and coalgebra. The point of this dissertation is to explore the area where the two meet. The thesis of this dissertation is that the right kind of monads to describe the observable behaviour of programs are completely iterative monads (cims), introduced by Elgot and more recently studied by Adamek and others. They are monads equipped with a certain corecursion scheme that allows us to describe the computation in a coinductive, step-wise manner. To support this, we introduce a formal coinductive semantics parametrised with a cim. We study its properties and show that it instantiates to a number of known approaches, based on metric spaces and final coalgebras. Then, we focus on studying properties of cims, especially those important in semantics and programming, like composability. We show that a number of constructions used in denotational semantics to model different aspects of behaviour are instances of the constructions that we introduce. The most important structure that we study are coinductive resumptions, generalising previous results by Moggi or Hyland, Plotkin, and Power. The language of our development is category-theoretic, and so are the properties that we investigate. We are interested in universal properties, distributive laws, algebras, and monadicity. Thus, the results apply not only to semantics and programming, but can be construed as a general investigation of algebraic structures with iteration.

gekürzte Fassung: Coalgebren wurden sowohl in der Mathematik (seit den 70er Jahren) als auch in der theoretischen Informatik (seit den 90er Jahren) untersucht. In der Mathematik sind Coalgebren dual zu universellen Algebren definiert. Sie bestehen aus einer Trägermenge A zusammen mit Cofunktionen ? : A ? , die A in die n-fache disjunkte Vereinigung von sich selbst abbilden. Das Ziel der Forschung ist hier vor allem, duale Versionen von Definitionen und Resultaten aus der universellen Algebra für die Welt der Coalgebren zu finden. Die theoretische Informatik betrachtet Coalgebren von kategorieller Seite aus. Für einen gegebenen Funktor F : C ? C sind Coalgebren als Paare (S,"alpha") definiert, wobei S ein Objekt von C und "alpha" : S ? F(S) ein Morphismus in C ist. Somit stellt der obige Ansatz mit Cofunktionen einen Spezialfall dar. Begriffe wie Homomorphismus oder Bisimularität lassen sich auf einfache Weise ausdrücken und handhaben. Solche Coalgebren modellieren eine große Anzahl von dynamischen Systemen. Das liefert eine kanonische und vereinheitlichende Sicht auf diese Systeme. Die vorliegende Dissertation führt beide genannten Forschungsrichtungen der Coalgebren weiter: Teil I beschäftigt sich mit "klassischen" Coalgebren, also solchen, wie sie in der universellen Algebra untersucht werden. Insbesondere wird das Verhältnis zur Klontheorie erforscht. Teil II der Arbeit widmet sich dem kategoriellen Ansatz aus der theoretischen Informatik. Von speziellem Interesse ist hier die Anwendung von Coalgebren zur Spezifikation von Systemen. Coalgebren und Klontheorie In der universellen Algebra spielen Systeme von Funktionen eine bedeutende Rolle, u.a. in der Klontheorie. Dort betrachtet man Funktionen auf einer festen gegebenen Grundmenge. Klone von Funktionen sind Mengen von Funktionen, die alle Projektionen enthalten und die gegen Superposition (d.h. Einsetzen) abgeschlossen sind. Extern lassen sich diese Klone als Galois-abgeschlossene Mengengzgl. der Galois-Verbindung zwischen Funktionen und Relationen darstellen. Diese Galois-Verbindung wird durch die Eigenschaft einer Funktion induziert, eine Relation zu bewahren. Dual zu Klonen von Funktionen wurde von B. Csákány auch Klone von Cofunktionen untersucht. Folglich stellt sich die Frage, ob solche Klone ebenfalls mittels einer geeigneten Galois-Verbindung charakterisiert werden können. Die vorliegende Arbeit führt zunächst den Begriff von Corelationen ein. Es wird auf kanonische Weise definiert, was es heißt, daß eine Cofunktion eine Corelation bewahrt. Dies mündet in einer Galois-Theorie, deren Galois-abgeschlossene Mengen von Cofunktionen tatsächlich genau die Klone von Cofunktionen sind. Überdies entsprechen die Galois-abgeschlossenen Mengen von Corelationen genau den Klonen von Corelationen. Die Galois-Theorien von Funktionen und Relationen einerseits und Cofunktionen und Corelationen anderseits sind sich sehr ähnlich. Das wirft die Frage auf, welche Voraussetzungen allgemein nötig sind, um solche und ähnliche Galois-Theorien aufzustellen und die entsprechenden Galois-abgeschlossenen Mengen zu charakterisieren. Das Ergebnis ist eine Metatheorie, bei der die Gemeinsamkeiten in den Charakterisierungen der Galois-abgeschlossenen Mengen herausgearbeitet sind. Bereits bekannte Galois-Theorien erweisen sich als Spezialfälle dieser Metatheorie, und zwar die Galois-Theorien von partiellen Funktionen und Relationen, von mehrwertigen Funktionen und Relationen und von einstelligen Funktionen und Relationen....

gekürzte Fassung: Coalgebren wurden sowohl in der Mathematik (seit den 70er Jahren) als auch in der theoretischen Informatik (seit den 90er Jahren) untersucht. In der Mathematik sind Coalgebren dual zu universellen Algebren definiert. Sie bestehen aus einer Trägermenge A zusammen mit Cofunktionen ? : A ? , die A in die n-fache disjunkte Vereinigung von sich selbst abbilden. Das Ziel der Forschung ist hier vor allem, duale Versionen von Definitionen und Resultaten aus der universellen Algebra für die Welt der Coalgebren zu finden. Die theoretische Informatik betrachtet Coalgebren von kategorieller Seite aus. Für einen gegebenen Funktor F : C ? C sind Coalgebren als Paare (S,"alpha") definiert, wobei S ein Objekt von C und "alpha" : S ? F(S) ein Morphismus in C ist. Somit stellt der obige Ansatz mit Cofunktionen einen Spezialfall dar. Begriffe wie Homomorphismus oder Bisimularität lassen sich auf einfache Weise ausdrücken und handhaben. Solche Coalgebren modellieren eine große Anzahl von dynamischen Systemen. Das liefert eine kanonische und vereinheitlichende Sicht auf diese Systeme. Die vorliegende Dissertation führt beide genannten Forschungsrichtungen der Coalgebren weiter: Teil I beschäftigt sich mit "klassischen" Coalgebren, also solchen, wie sie in der universellen Algebra untersucht werden. Insbesondere wird das Verhältnis zur Klontheorie erforscht. Teil II der Arbeit widmet sich dem kategoriellen Ansatz aus der theoretischen Informatik. Von speziellem Interesse ist hier die Anwendung von Coalgebren zur Spezifikation von Systemen. Coalgebren und Klontheorie In der universellen Algebra spielen Systeme von Funktionen eine bedeutende Rolle, u.a. in der Klontheorie. Dort betrachtet man Funktionen auf einer festen gegebenen Grundmenge. Klone von Funktionen sind Mengen von Funktionen, die alle Projektionen enthalten und die gegen Superposition (d.h. Einsetzen) abgeschlossen sind. Extern lassen sich diese Klone als Galois-abgeschlossene Mengengzgl. der Galois-Verbindung zwischen Funktionen und Relationen darstellen. Diese Galois-Verbindung wird durch die Eigenschaft einer Funktion induziert, eine Relation zu bewahren. Dual zu Klonen von Funktionen wurde von B. Csákány auch Klone von Cofunktionen untersucht. Folglich stellt sich die Frage, ob solche Klone ebenfalls mittels einer geeigneten Galois-Verbindung charakterisiert werden können. Die vorliegende Arbeit führt zunächst den Begriff von Corelationen ein. Es wird auf kanonische Weise definiert, was es heißt, daß eine Cofunktion eine Corelation bewahrt. Dies mündet in einer Galois-Theorie, deren Galois-abgeschlossene Mengen von Cofunktionen tatsächlich genau die Klone von Cofunktionen sind. Überdies entsprechen die Galois-abgeschlossenen Mengen von Corelationen genau den Klonen von Corelationen. Die Galois-Theorien von Funktionen und Relationen einerseits und Cofunktionen und Corelationen anderseits sind sich sehr ähnlich. Das wirft die Frage auf, welche Voraussetzungen allgemein nötig sind, um solche und ähnliche Galois-Theorien aufzustellen und die entsprechenden Galois-abgeschlossenen Mengen zu charakterisieren. Das Ergebnis ist eine Metatheorie, bei der die Gemeinsamkeiten in den Charakterisierungen der Galois-abgeschlossenen Mengen herausgearbeitet sind. Bereits bekannte Galois-Theorien erweisen sich als Spezialfälle dieser Metatheorie, und zwar die Galois-Theorien von partiellen Funktionen und Relationen, von mehrwertigen Funktionen und Relationen und von einstelligen Funktionen und Relationen....

A fundamental component of theoretical computer science is the application of logic. Logic provides the formalisms by which we can model and reason about computational questions, and novel computational features provide new directions for the development of logic. From this perspective, the unusual features of quantum computation present both challenges and opportunities for computer science. Our existing logical techniques must be extended and adapted to appropriately model quantum phenomena, stimulating many new theoretical developments. At the same time, tools developed with quantum applications in mind often prove effective in other areas of logic and computer science. In this thesis we explore logical aspects of this fruitful source of ideas, with category theory as our unifying framework. Inspired by the success of diagrammatic techniques in quantum foundations, we begin by demonstrating the effectiveness of string diagrams for practical calculations in category theory. We proceed by example, developing graphical formulations of the definitions and proofs of many topics in elementary category theory, such as adjunctions, monads, distributive laws, representable functors and limits and colimits. We contend that these tools are particularly suitable for calculations in the field of coalgebra, and continue to demonstrate the use of string diagrams in the remainder of the thesis. Our coalgebraic studies commence in chapter 3, in which we present an elementary formulation of a representation result for the unitary transformations, following work developed in a fibrational setting in [Abramsky, 2010]. That paper raises the question of what a suitable "fibred coalgebraic logic" would be. This question is the starting point for our work in chapter 5, in which we introduce a parameterized, duality based frame- work for coalgebraic logic. We show sufficient conditions under which dual adjunctions and equivalences can be lifted to fibrations of (co)algebras. We also prove that the semantics of these logics satisfy certain "institution conditions" providing harmony between syntactic and semantic transformations. We conclude by studying the impact of parameterization on another logical aspect of coalgebras, in which certain fibrations of predicates can be seen as generalized invariants. Our focus is on the lifting of coalgebra structure along a fibration from the base category to an associated total category of predicates. We show that given a suitable parameterized generalization of the usual liftings of signature functors, this induces a "fibration of fibrations" capturing the relationship between the two different axes of variation.

Demonstramos um teorema da correspondência do tipo Galois para ações de álgebras de Hopf pontuais de dimensão finita em álgebras primas. A correspondência acontece entre subálgebras racionalmente completas e comódulo subálgebras. As subálgebras racionalmente completas são subálgebras da álgebra prima, enquanto os comódulo subálgebras são comódulo subálgebras do produto smash entre o centralizador da álgebra prima em sua álgebra de quocientes de Martindale simétrica e a álgebra de Hopf. / A Galois-type correspondence theorem for prime algebras acted upon by a finite dimensional pointed Hopf algebra is proved. The correspondence involves rationally complete subalgebras and comodule subalgebras. The rationally complete subalgebras are subalgebras of the prime algebra, while the comodule subalgebras are comodule subalgebras of the smash product between the centralizer of the prime algebra in its symmetric Martindale quotient algebra and the Hopf algebra.

Demonstramos um teorema da correspondência do tipo Galois para ações de álgebras de Hopf pontuais de dimensão finita em álgebras primas. A correspondência acontece entre subálgebras racionalmente completas e comódulo subálgebras. As subálgebras racionalmente completas são subálgebras da álgebra prima, enquanto os comódulo subálgebras são comódulo subálgebras do produto smash entre o centralizador da álgebra prima em sua álgebra de quocientes de Martindale simétrica e a álgebra de Hopf. / A Galois-type correspondence theorem for prime algebras acted upon by a finite dimensional pointed Hopf algebra is proved. The correspondence involves rationally complete subalgebras and comodule subalgebras. The rationally complete subalgebras are subalgebras of the prime algebra, while the comodule subalgebras are comodule subalgebras of the smash product between the centralizer of the prime algebra in its symmetric Martindale quotient algebra and the Hopf algebra.

This thesis is about coalgebraic methods in software specification and verification. It extends known techniques of coalgebraic specification to a more general level to pave the way for real world applications of software verification. There are two main contributions of the present thesis: 1. Chapter 3 proposes a generalisation of the familiar notion of coalgebra such that classes containing methods with arbitrary types (including binary methods) can be modelled with these generalised coalgebras. 2. Chapter 4 presents the specification language CCSL (short for Coalgebraic Class Specification Language), its syntax, its semantics, and a prototype compiler that translates CCSL into higher-order logic. / Die Dissertation beschreibt coalgebraische Mittel und Methoden zur Softwarespezifikation und -verifikation. Die Ergebnisse dieser Dissertation vereinfachen die Anwendung coalgebraischer Spezifikations- und Verifikationstechniken und erweitern deren Anwendbarkeit. Damit werden Softwareverifikation im Allgemeinen und im Besonderen coalgebraische Methoden zur Softwareverifikation der praktischen Anwendbarkeit ein Stück nähergebracht. Diese Dissertation enthält zwei wesentliche Beiträge: 1. Im Kapitel 3 wird eine Erweiterung des klassischen Begriffs der Coalgebra vorgestellt. Diese Erweiterung erlaubt die coalgebraische Modellierung von Klassenschnittstellen mit beliebigen Methodentypen (insbesondere mit binären Methoden). 2. Im Kapitel 4 wird die coalgebraische Spezifikationssprache CCSL (Coalgebraic Class Specification Language) vorgestellt. Die Bescheibung umfasst Syntax, Semantik und einen Prototypcompiler, der CCSL Spezifikationen in Logik höherer Ordnung (passend für die Theorembeweiser PVS und Isabelle/HOL) übersetzt.

<p>In the first part of this thesis, we contribute to the semantics of typed object calculus by giving (a) a category-theoretic denotational semantics using partial maps making use of an algebraic compactness assumption, (b) a notion of "wrappers'' by which algebraic datatypes can be represented as object types, and (c) proofs of computational soundness and adequacy of typed object calculus via Plotkin's FPC (with lazy operational semantics), thus making models of FPC suitable also for first-order typed object calculus (with recursive objects supporting method update, but not subtyping). It follows that a valid equation in the model induces operationally congruent terms in the language, so that program algebras can be studied. For (c), we also develop an extended first-order typed object calculus, and prove subject reduction. The second part of the thesis concerns recursion principles on datatypes including the untyped lambda calculus as a special case. Freyd showed that in certain domain theoretic categories, locally continuous functors have minimal invariants, which possess a structure that he termed dialgebra. This gives rise to a category of dialgebras and homomorphisms, where the minimal invariants are initial, inducing a powerful recursion scheme (direcursion) on a complete partial order. We identify a problem that appears when we translate (co)iterative functions to direcursion, and as a solution to this problem we develop a recursion scheme (primitive direcursion). This immediately gives a number of examples of direcursive functions, improving on the situation in the literature where only a few examples have appeared. By means of a case study, this line of work is connected to object calculus models.</p> / Delarbete II är även publicerad som Teknisk rapport, 2007, Oct, No2.

In the first part of this thesis, we contribute to the semantics of typed object calculus by giving (a) a category-theoretic denotational semantics using partial maps making use of an algebraic compactness assumption, (b) a notion of "wrappers'' by which algebraic datatypes can be represented as object types, and (c) proofs of computational soundness and adequacy of typed object calculus via Plotkin's FPC (with lazy operational semantics), thus making models of FPC suitable also for first-order typed object calculus (with recursive objects supporting method update, but not subtyping). It follows that a valid equation in the model induces operationally congruent terms in the language, so that program algebras can be studied. For (c), we also develop an extended first-order typed object calculus, and prove subject reduction. The second part of the thesis concerns recursion principles on datatypes including the untyped lambda calculus as a special case. Freyd showed that in certain domain theoretic categories, locally continuous functors have minimal invariants, which possess a structure that he termed dialgebra. This gives rise to a category of dialgebras and homomorphisms, where the minimal invariants are initial, inducing a powerful recursion scheme (direcursion) on a complete partial order. We identify a problem that appears when we translate (co)iterative functions to direcursion, and as a solution to this problem we develop a recursion scheme (primitive direcursion). This immediately gives a number of examples of direcursive functions, improving on the situation in the literature where only a few examples have appeared. By means of a case study, this line of work is connected to object calculus models. / Delarbete II är även publicerad som Teknisk rapport, 2007, Oct, No2.

This thesis is about coalgebraic methods in software specification and verification. It extends known techniques of coalgebraic specification to a more general level to pave the way for real world applications of software verification. There are two main contributions of the present thesis: 1. Chapter 3 proposes a generalisation of the familiar notion of coalgebra such that classes containing methods with arbitrary types (including binary methods) can be modelled with these generalised coalgebras. 2. Chapter 4 presents the specification language CCSL (short for Coalgebraic Class Specification Language), its syntax, its semantics, and a prototype compiler that translates CCSL into higher-order logic. / Die Dissertation beschreibt coalgebraische Mittel und Methoden zur Softwarespezifikation und -verifikation. Die Ergebnisse dieser Dissertation vereinfachen die Anwendung coalgebraischer Spezifikations- und Verifikationstechniken und erweitern deren Anwendbarkeit. Damit werden Softwareverifikation im Allgemeinen und im Besonderen coalgebraische Methoden zur Softwareverifikation der praktischen Anwendbarkeit ein Stück nähergebracht. Diese Dissertation enthält zwei wesentliche Beiträge: 1. Im Kapitel 3 wird eine Erweiterung des klassischen Begriffs der Coalgebra vorgestellt. Diese Erweiterung erlaubt die coalgebraische Modellierung von Klassenschnittstellen mit beliebigen Methodentypen (insbesondere mit binären Methoden). 2. Im Kapitel 4 wird die coalgebraische Spezifikationssprache CCSL (Coalgebraic Class Specification Language) vorgestellt. Die Bescheibung umfasst Syntax, Semantik und einen Prototypcompiler, der CCSL Spezifikationen in Logik höherer Ordnung (passend für die Theorembeweiser PVS und Isabelle/HOL) übersetzt.