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:
- 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.
- 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.
- Cynthia Bailey Lee wrote a paper on political cartoons for
CSE 271 in 2003.
- Dana Dahlstrom and Vinu Somayaji wrote the Tutorial on Semiotics for CSE 271 in 2004.
- 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.
- 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
- [New]
Style as Choice of Blending Principles, by Joseph Goguen and Fox
Harrell. In Proceedings, Symposium on Style and
Meaning in Language, Art, Music and Design, in the 2004 AAAI Fall
Symposium Series in Washington DC, Oct 21-24. There is also a postscript version. This paper proposes a new
approach to style based on the principles for blending that works employ; it
also includes an implementation approach to syntax based on structural
blending and cognitive grammar, and proposes a reconsideration and
generalization of optimality principles for blending. A poetry generation
system based on this ideas is also explained, and some output is included.
- [New]
Foundations for Active Multimedia Narrative: Semiotic spaces and
structural blending, by Joseph Goguen and Fox Harrell. To appear in
Interaction Studies: Social Behaviour and Communication in Biological and
Artificial Systems. This includes a description of an algorithm for
conceptual blending, and its application to the generation of novel metaphors
in poetry. Here is a short press release related to this
project.
- [New] Steps
towards a Design Theory for Virtual Worlds, by Joseph Goguen. In
Developing Future Interactive Systems, edited by Maribel
Sanchez-Segura, published by Idea Group. This sketches algebraic semiotics
and its applications, including user interface design and scientific
visualization.
- Semiotic Morphisms, Representations, and
Blending for User Interface Design, by Joseph Goguen. Keynote
lecture, in Proceedings,
AMAST Workshop on Algebraic Methods in Language Processing, edited by
Fausto Spoto, Giuseppi Scollo and Anton Nijholt, AMAST Press, 2003, pages
1-15. Workshop held Verona, Italy, 25 - 27 August 2003. This paper shows
how hidden algebra extends algebraic semiotics to handle interaction. A pdf version of the paper is also available.
- [New] Musical
Qualia, Context, Time, and Emotion, a paper on the philosophy and
cognitive science of music, in Art, Brain,
and Consciousness, the third volume in the Art and the Brain
series, with a special focus on music. A pdf
version is also available. (Although algebraic semiotics is not a major
focus of this paper, it does use some blending.)
- [New]Extended abstract of Sync or Swarm: Group Dynamics in Musical Free
Improvisation, by David Borgo and Joseph Goguen, and shorter abstract. The short abstract is in
Proceedings, Conference on Interdisciplinary Musicology,
Dept. Musicology, University of Graz, 2004, pages 52-53, and the extended
abstract is in the attached CD. Held in Graz, Austria, 15-18 April 2004.
Sorry, both are in MS Word. (This paper makes only marginal use of algebraic
semiotics.)
- Information Visualization and
Semiotic Morphisms, by Joseph Goguen and D. Fox Harrell. An informal
introduction to the notion of semiotic morphism, showing how information
visualization, in both analysis and design, can benefit from a viewpoint based
on structure-preserving morphisms. To appear in Multidisciplinary
Approaches to Visual Representations and Interpretations, ed. Grant
Malcolm (Elsevier 2004), pages 93-106.
- Semiotics, Compassion and
Value-Centered Design, by Joseph Goguen. Keynote address, at the Organizational Semiotics
Workshop, University of Reading, UK, 11 July 2003. Discusses the
informal application of algebraic semiotics to large scale design problems,
such as organizations, and discusses the role of compassion.
- Web-based Support for Cooperative
Software Engineering, by Joseph Goguen and Kai Lin. In Annals of Software Engineering,
volume 12, No. 1, pages 167-191, 2001, special issue on multimedia software
engineering, edited by Jeffrey Tsai. This is an overview of the Tatami
project, featuring version 4 of the Kumo proof assistant and website
generator, and focusing on its design decisions, its use of multimedia web
capabilities, and its integration of formal and informal methods for software
development in a distributed cooperative environment.
- An Introduction to Algebraic Semiotics, with
Applications to User Interface Design, by Joseph Goguen, in Computation for Metaphor, Analogy
and Agents, edited by Chrystopher Nehaniv, Springer Lecture Notes in
Artificial Intelligence, volume 1562, 1999, pages 242-291. This is the
original paper on the mathematical foundations of algebraic semiotics, with
3/2-categories, 3/2-colimits, and many examples, especially from user
interface design.
- Towards a Social, Ethical Theory of
Information, in Social Science Research, Technical Systems and
Cooperative Work, edited by Geoffrey Bowker, Les Gasser, Leigh Star and
William Turner (Erlbaum, 1997) pages 27-56. A theory of information based on
social interaction; this provides the social foundations for algebraic
semiotics.
- Reality and Human Values in
Mathematics, by Joseph Goguen, submitted for publication. 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.
- Notes on Narrative, by Joseph Goguen. Brief overview of some techniques
for the analysis of stories, including summaries of the structural theory of
narrative, and techniques for the extraction of value systems from stories.
Somewhat edited in May 2001.
- Social and Semiotic Analyses for Theorem
Prover User Interface Design, by Joseph
Goguen, in Formal Aspects of Computing, volume 11, pages 272-301,
1999. A systematic justification of the style guidelines for proof websites
generated by Kumo, based on algebraic semiotics, narratology, and other
fields.
- Signs and Representations: Semiotics for
User Interface Design, by Grant Malcolm and Joseph Goguen, in Visual Representations and
Interpretations, edited by Ray Paton and Irene Nielson, Springer Workshops
in Computing, 1998 (proceedings of a workshop held in Liverpool), pages
163-172. An informal introduction to algebraic semiotics with examples,
including aspects of operating system interfaces.
- An Overview of the Tatami Project,
by Joseph Goguen, Kai Lin, Grigore
Rosu, Akira Mori and Bogdan Warinschi, in Cafe: An Industrial-Strength
Algebraic Formal Method, edited by Kokichi Futatsugi, Tetsuo Tamai and
Ataru Nakagawa, Elsevier, 2000, pages 61-78. This is a high level snapshop of
the UCSD Tatami project as of late 1999. See
also the brief report by Prof. Rod
Burstall, the brief summary of results
as of Sept. 2001, and the one page progress summary for our NSF grant up
to October 1999, Hidden Algebra and
Concurrent Distributed Software, which appeared in Software Engineering Notes.
- Requirements Engineering as the
Reconciliation of Technical and Social Issues, in Requirements
Engineering: Social and Technical Issues, edited with Marina Jirotka
(Academic Press, 1994) pages 165-199. This discusses situated abstract data
types, a precursor of our current algebraic notion of sign system; however
there is a greater emphasis on social context, and some suggestive examples.
ISBN 0-1238-5335-4.
- On Notation, by Joseph Goguen. Some basics of Peircean semiotics with
easy applications to computer science and mathematics. Revised version of a
paper in TOOLS 10: Technology of Object-Oriented Languages and Systems,
edited by Boris Magnusson, Bertrand Meyer and Jean-Francois Perrot
(Prentice-Hall, 1993) pages 5-10.
- Formality and Informality in Requirements
Engineering, in Proceedings, Fourth International Conference on
Requirements Engineering (IEEE Computer Society, April 1996) pages
102-108. This keynote address gives an overview of our work in requirements
capture and analysis, up to mid-1996.
- Formal Tools for Distributed Cooperative
Engineering, by Joseph Goguen, Kai Lin, Akira Mori and Grigore Rosu. Describes how the Tatami system
and the Kumo proof assistant and website generator integrate formal and
informal methods for software development, in a distributed cooperative
environment. A verification step can be the scan of and envelope back, a
diagram or applet, as well as a fully formal subproof. In Proceedings,
CafeOBJ Symposium (26-29 April 1998, Kyoto, Japan). (This is a bit out of
date.)
- Distributed Cooperative Formal Methods
Tools, by Joseph Goguen, Kai Lin, Akira Mori, Grigore Rosu and Akiyoshi Sato. Overview of
Tatami project tools and methods, including hidden algebra and algebraic
semiotics, with examples. Proceedings, Automated Software Engineering
(Lake Tahoe NV, 3-5 Nov 1997), IEEE, pages 55-62. (This is a bit out of
date.)
- What is a Proof? by Joseph Goguen. Informal essay written for user interface design
course, CSE 271; original from April 1997, with
most recent edits from July 2001.
- Algebraic Semiotics, ProofWebs and
Distributed Cooperative Proving, with Akira Mori and Kai Lin. Describes the Tatami proofweb data structure and
the Kumo proof assistant and website generator system, plus methods from
semiotics used in their design, with examples. In Proceedings, User
Interfaces for Theorem Provers (Sophia Antipolis, France, 1-2 Sept 1997),
pages 25-34. (This is now out of date.)
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.
Other
Links
- [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.
- 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
- 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
Last modified: Wed Mar 30 08:12:59 PST 2005