Browse Prior Art Database

SOME FUNDAMENTALS OF ORDER-ALGEBRAIC SEMANTICS

IP.com Disclosure Number: IPCOM000148719D
Original Publication Date: 1976-May-28
Included in the Prior Art Database: 2007-Mar-30
Document File: 18 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Wagner, E.G.: AUTHOR [+5]

Abstract

RC 6020 SOME FUNDAMENTALS OF ORDER-ALGEBRAIC SEMALUTI cs

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 18

RC 6020 SOME FUNDAMENTALS OF ORDER-ALGEBRAIC SEMALUTI

(26076)
51 281 76 E.G.Wagner, J.B.Wright, ~ . ~ . ~ o ~ u e n ' ,
and 3.W.Thatcher .f t

Camp er ci Mathematical Sciences Department Mathematics IBM Thomas J. Watson Research Center

Yorktown Heights, New York 10598

Typed by Martha Pierce on MT.ST

ABSTRACT: The order-theoretic enrichment of the algebraic approach to theoretical computer science, and to the theory
of programming in particular, can be accomplished rather directly and elegantly, and appears to have a wide range of applications. This paper presents mathematical fundamentals of order-algebraic semantics. The principal new results con- cern free continuous algebraic theories and minimal conditions for solving general "systems of (recursive) equations" in algebraic theories.

* To be presented at the Symposium on Mathematical Founda- tions of Computer Science, ~dafisk, Poland, September 1976. Proceedings to be published by Springer-Verlag in Lecture Notes in Computer Science.

--

t Currently: Computer Science Department, UCLA, Los Angeles, C?lifornia 90024. Partial support received from the University of Colorado and Naropa Institute, both of Boulder, Colorado 80302.

This set of authors is herein, and we hope subsequently will

iz,

cs *

16 pages

''

referred to by the symbols ADJ.

[This page contains 1 picture or other non-text object]

Page 2 of 18

LISIITED DISTRIBUTIOE NOTICE

.This report has been submitted for publication elsewhere and has been issued as a Research Report for early dissemination
of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:
IBhl Thomas J. Fatson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 18

1. Introduction

    Order-theoretic and algebraic methods have played a major role i n theoretical computer science. Particularly in the theory of programming, there has been a stead- ily increasing flow of papers which combine the two approaches. We believe this lit- erature deserves, indeed requires, a. mathematics i n which the order-theoretic and algebraic approaches are truly joined. This paper presents a basis for such a devel- opment.

    This material grew out of work on inital algebra semantics reported in ADJ (1975). For ease of access, that paper used only universal algebra, and in particular, no category theory despite the authors' general advocacy of that approach (ADJ (1976)). However, proofs of some results i n the first versions of ADJ (1975), which were quite unwieldy in the universal algebra framework, are much simpler in a categorical frame- work.

    Fortunately the essential concept of algebraic theory (Lawvere (1963)) requires very l i t t l e category theory. Thus, this paper assume...