Algebraic Semiotics
Contents
Short Overview

Algebraic semiotics is a new approach to meaning and representation, and in particular to user interface design, that builds on five important insights from the last hundred years:

• Semiotics: Signs are not isolated items; they come in systems, and the structure of a sign is to a great extent inherited from the system to which it belongs. Signs do not have pre-given "Platonic" meanings, but rather their meaning is relational, because signs are always interpreted in particular contexts. (The first sentence reflects the influence of Saussure, the second that of Pierce.)
• Social Context: Signs are used by people as part of their participation in social groups; meaning is primarily a social phenomenon; its purpose is communication. (This reflects some concerns of post-structuralism.)
• Morphisms: If some class of objects is interesting, then structure preserving maps or morphisms of those objects are also interesting - perhaps even more so. For semiotics, these morphisms are representations. Objects and morphisms together form structures known as categories.
• Blending and Colimits: If some class of objects is interesting, then putting those objects together in various ways is probably also interesting. Morphisms can be used to indicate that certain subojects are to be shared in such constructions, and colimits of various kinds are a category theoretic formalization of ways to put objects together. In cognitive linguistics, blending has been identified as an important way to combine conceptual systems.
• Algebraic Specification: Sign systems and their morphisms can be described and studied in a precise way using semantic methods based on equational logic that were developed for the theory of abstract data types.
Semiotics is the study of signs. Our research attempts to make this area more systematic, rigorous, and applicable, as well as to do justice to its social and cognitive foundations. Algebraic semiotics combines aspects of algebraic specification and social semiotics. It has been applied to information visualization, user interface design, the representation of mathematical proofs, multimedia narrative, virtual worlds, and metaphor generation, among other things. The webnote Semiotic Morphisms is a mostly non-technical exposition of some basics of algebraic semiotics, and the course CSE 271 includes more of the same plus many applications. See also the User Interface Design homepage. More detailed technical information may be found in Semiotic Morphisms, Representations, and Blending for User Interface Design, Foundations for Active Multimedia Narrative: Semiotic spaces and structural blending, and An Introduction to Algebraic Semiotics, with Applications to User Interface Design.

A basic concept is that of a semiotic morphism, which provides representations in one sign system (the target) for signs from another (the source). Semiotic morphisms can be partial, i.e., they do not necessarily have to preserve all of the signs or all the structure of the source system. The degree to which semiotic morphisms preserve various features provides a basis for comparing the quality of representations, and leads to an interesting study of trade-offs.

To illustrate these ideas, consider proofs (in some fixed logical system) as forming a sign system; an extension of this system includes additional information to help with understanding proofs, such as motivation, background tutorials, and examples. Another sign system is given by website technology (HTML, JavaScript, XML, etc.). Then representations of proofs as websites are morphisms from the first system (or its extension) to the second, and the orderings on semiotic morphisms compare aspects of the quality of such representations. Some website design principles, called the Tatami conventions, were extracted from our study and embodied in our Kumo tool, which combines proof assistant and website generation capabilities; it generates so-called "proofweb" data structures that use HTML, JavaScript, etc., which can then be viewed with any browser. For more details, see Web-based Support for Cooperative Software Engineering. Some other applications are discussed in Information Visualization and Semiotic Morphisms and in Steps towards a Design Theory for Virtual Worlds.

The "world famous" UC San Diego Semiotic Zoo contains a collection of semiotic morphisms, each an example of bad design arising through failure to preserve some relevant structure. (Notes: (1) The zoo still has one wing under construction; and (2) it won a "Creativity Award" from Art & Technology.)

Mathematical foundations can be provided by the rather recent and very abstract field called "category theory" (it is not related to the area of psychology of the same name), by noting that sign systems together with semiotic morphisms form a category. Some modest additional axioms are satisfied, which leads to the notion of a 3/2-category. An appropriate notion of colimit for such categories has properties that make it suitable for studying the blending of sign systems, as explained in An Introduction to Algebraic Semiotics, with Applications to User Interface Design. See also Semiotic Morphisms, Representations, and Blending for User Interface Design, to see how hidden algebra extends algebraic semiotics to handle interaction. The more recent papers Foundations for Active Multimedia Narrative: Semiotic spaces and structural blending and Information Visualization and Semiotic Morphisms include more intuitive introductions to many issues, and the webnote Semiotic Morphisms may be a convenient place for many readers to start.

Some Concrete Applications

The following are some projects that used algebraic semiotics in various ways:

1. Henry Mitchell and Breese Stevens built a website for San Diego Jazz Party, a non-profit organization that organizes a once a year weekend jazz festival, with profits supporting music in the San Diego school system.
2. Abigail Gray built a website for a network of San Diego animal shelters; her MS thesis documents the use of algebraic semiotics for many design decisions.
3. Cynthia Bailey Lee wrote a paper on political cartoons for CSE 271 in 2003.
4. Dana Dahlstrom and Vinu Somayaji wrote the Tutorial on Semiotics for CSE 271 in 2004.
5. The "world famous" UC San Diego Semiotic Zoo contains a collection of semiotic morphisms, each an example of bad design arising through failure to preserve some relevant structure.
6. A collection of proof displays generated by version 4 of the Kumo proof assistant and website generator, as part of the Tatami project, a goal of which is to make machine proofs much more readable than is usual.

Social Foundations

Towards a Social, Ethical Theory of Information describes a theory of information based on social interaction. This theory provides a social foundation for algebraic semiotics, in which some ideas from ethnomethodology play a key role. Ethnomethodology is a branch of sociology that studies ordinary natural social interaction; it has especially considered conversation. In this framework, we may define a sign system to be a system of distinctions, grounded in the ordinary practices of some social group, and used for communication within that group. Signs are the "items" that are so distinguished.

Signs and sign systems are grounded in the actual practices of particular groups. Some sign systems are used by analysts of a group, rather than by members of that group. For example, formal grammars are used by linguists to study a language; they are not ordinarily used by the speakers of that language. Of course, analysts also form their own social groups.

Values are an inherent part of any social group, and the concepts (including distinctions) and methods that a group uses naturally reflect those values. Therefore analysts can hope to derive values by observing members' concepts and methods. One might go so far as to say that social groups, values, and communication are coemergent, in the sense that each produces and sustains the others.

Requirements Engineering as the Reconciliation of Technical and Social Issues discusses situated abstract data types, which are a precursor of our current algebraic notion of sign system, with a greater emphasis on social context, and with some examples showing how representation interacts with social context. See also Reality and Human Values in Mathematics, which applies discourse analysis (in the sense of sociolinguistics), cognitive linguistics and ethnomethodology to mathematical discourse, showing how the reality of mathematical objects is achieved, and the role of values in this process; a pdf version is also available.

Brief Annotated Bibliography
Background information on algebraic specification and category theory can be found in the following:
• Algebraic Semantics of Imperative Programs, by Joseph Goguen and Grant Malcolm (MIT Press, 1996). Contains entry level introductions to universal algebra and the OBJ3 language. An Executable Course in the Algebraic Semantics of Imperative Programs discusses some pedagogical innovations of this book.

• Introducing OBJ, essentially the OBJ3 user manual, from Software Engineering with OBJ: algebraic specification in practice, edited by Joseph Goguen and Grant Malcolm, Kluwer, April 2000; ISBN 0-7923-7757-5. The book is a general introduction to OBJ and its applications; its Introduction and table of contents are also available.

• Two chapters from Theorem proving and Algebra, by Joseph Goguen, to be published by MIT Press, someday. This book provides systematic introductions to general algebra and its applications in computer science, especially term rewriting and theorem proving. Chapter 1, Introduction and Chapter 8, First Order Logic, plus the References and the Table of Contents. Chapter 8 is an elegant algebraic exposition of first order logic, proof planning and induction; the treatment of induction is unusually general.

• A Categorical Manifesto, in Mathematical Structures in Computer Science, Volume 1, Number 1, March 1991, pages 49-67. Intuitive motivation for all the basic concepts of category theory, with many computer science examples.

• What is Unification?, in Resolution of Equations in Algebraic Structures, Volume 1: Algebraic Techniques, edited by Maurice Nivat and Hassan Ait-Kaci (Academic Press, 1989) pages 217-261. An introductory exposition of some basic categorical concepts, with applications to the theory of unification.

• [New] Website of
• Future Interactive Media, CSE 87B, Winter 2005; an undergraduate seminar. See also Computational Narratology, CSE 87C, Winter 2004.

• CSE 271: User Interface Design: Social and Technical Issues. A course introducing user interface design, algebraic semiotics, blending, information visualization, and more. See also CSE 171 for an undergraduate version of similar material.

• Website on blending, with applications to metaphor; work of Gilles Fauconnier, Mark Turner and others, in the area of cognitive linguistics. (An Introduction to Algebraic Semiotics, with Applications to User Interface Design gives a mathematical formalization of blending.)

• Bibliography on semiotics and information at Aalborg University, Denmark, maintained by Peter Bogh Andersen.

• Extensive semiotics on the web index at City University of Denver; many links, some interesting.

• Website on semiotics at National Institute of Standards and Technology; emphasizes practical applications.

• Bakhtin Centre homepage at Sheffield University (UK).

• SCIP Project homepage (Semiotic Cognitive Information Processing) at Trier University (Germany).

• CSE 275: Social Aspects of Technology and Science. An introduction to the many roles that society plays in engineering design and scientific research. See also CSE 175: Social and Ethical Issues in Information Technology (formerly CSE 190B) for an undergraduate version of similar material, but with more emphasis on ethics.

• An Introduction to Semiotics for HCI, by Mihai Nadin, University of Wuppertal, Germany; motivation and some interesting historical background, for applying semiotics to interface design.

• Semiotics for Beginners, by Daniel Chandler, University of Wales, Aberystwyth; a good place to begin. There is a US mirror site.

• Ray Paton's Metaphor in Scientific Thinking Page at Liverpool University, England; see especially his paper Glue, Verb and Text Metaphors in Biology, from Acta Biotheoretica.

• Homepage of User Interfaces for Theorem Provers interest group and conferences.

• Best website I know on graphical design for the web, the Yale Style Manuual.

• Homepage of Mark Ackerman, at the University of Michigan; great stuff on CSCW, electronic media, etc.

• Homepage of Phil Agre: lots of interesting stuff on communication, media, privacy, politics, libraries, the net, and life.

• A collection of proof displays generated by version 4 Kumo proof assistant and website generator. This is part of the Tatami project, a goal of which is to make machine proofs much more readable than is usual; the project has some emphasis on behavioral proofs of distributed concurrent systems. The following proofs are currently available for your browsing pleasure:

• An inductive proof that 1+...+ n = n(n+1) / 2. This will give you a chance to explore Kumo's navigation and display conventions on a simple example.
• A coinductive proof of a behavioral property of a simple flag object. This illustrates some basics of the hidden algebra approach on a very simple example; it gives an especially clear explanation of the need for behavioral properties.
• Two proofwebs for some familiar inductive properties of lists. The first was generated by a duck score written at the beginning of this effort; it is striking that all the lemmas needed to complete the proof can be deduced from the way that an improving series of proof attempts fail. The second proofweb succeeds, and was generated by a duck score derived from the first just by reordering its goals so that the lemmas that were found necessary are proved in the correct order.
1. This early attempt at proving that the reverse of the reverse of a list is the list, takes a direct approach, and its explanations emphasize the way that the two lemmas that are needed to complete the proof can be deduced from the output produced by unsuccessful proof attempts; one of these lemmas is the associativity of append
2. Here are the complete proofs for all three inductive properties of lists, including the two lemmas that are needed to establish the main goal.
• A coinductive proof of the behavioral correctness of the array-with-pointer implementation of stack. This behavioral refinement proof requires introducing a non-trivial lemma, which can also be inferred from a prior proof attempt that fails without it.
• A behavioral refinement proof of the correctness of implementing sets with lists, using attribute coinduction.
• A simple inductive proof of a formula for the sum of the squares of the first n natural numbers. This example is deliberately very spare, and in particular has no explanations, in order to illustrate the default conventions that Kumo uses when a user supplies only the absolute minimum input.
• A somewhat detailed proof that the square root of 2 is irrational, illustrating the first order capabilities of Kumo. This uses and proves many auxiliary lemmas; see the directory listing. Note: This is still under construction; some explanations are missing.
In addition, you will find the following:
• tutorial material on hidden algebra (which won a "Key Resource Award in Formal Methods" from links2go), which is linked to other tutorials on first order logic, and proof planning;
• many user-supplied home and explanation pages;
• several illustrative Java applets; and
• live proof execution via an OBJ server.
Netscape 3.0 or later and some knowledge of hidden algebra are needed. This is version 4 of Kumo, implemented by Kai Lin. Eventually the Java source code will also be available for downloading via the Kumo homepage. Your feedback is very welcome: please send comments on the implementation to the implementer, Kai Lin, and comments on the explanations and the theory to Joseph Goguen. Work on this system was supported in part by grants from the National Science Foundation, and from the large international CafeOBJ Project; see also the CafeOBJ Press Release, and the UCSD mirror site of the CafeOBJ homepage at Japan Advanced Institute of Science and Technology (JAIST).

Maintained by Joseph Goguen
To the research projects index page