The first basic notion of algebraic semiotics is that of a sign system. This notion is intended to capture the systematic structure of complex signs, since in all but the simplest cases, most signs are composed from other signs. For example, in written natural language, sentences are composed from words, and words are composed from letters. Thus signs need not be the simple little things that we usually call "signs," like the letters of an alphabet, or a stop sign. For another example, user interfaces are often very complex systems that still can usefully be considered as single complex signs. Some other complex signs are a book, a series of books, or even a whole library; similarly, a movie or a series of movies can be considered as complex signs.
An important insight due to Ferdinand de Saussure  is that signs always come in systems. One example that he considered is the tense system for the verbs of a language; for example, in English, adding "ed" to the end of a present tense (regular) verb makes it past tense, and adding "will" in front makes it future tense, as in "walk", "walked", and "will walk". Saussure's emphasis on the structure of systems of signs rather than of isolated signs has been very influential, first under the banner of structuralism, and later post-structuralism; the anthropology of Levi-Strauss and the deconstructionism of Derrida are among the best known work in these two traditions.
A basic strategy for making complex combinations of signs easier to understand is to divide their potential parts into sorts, and then enforce rules for the ways in which each sort of part can be used. This reduction of the arbitrariness of sign composition makes it easier to see the structure of complex signs, and to extract pertinent information. For example, newspapers are composed from articles, ads, cartoons, tables, etc., while articles are composed from headlines, paragraphs, photos, diagrams, etc., and paragraphs are composed of sentences. The so-called "parts of speech" in traditional grammars are also sorts in this sense. We assume that sorts may have a hierarchical structure under a subsort or "inheritance" partial ordering. For example, since nouns are also noun phrases, the sort NOUN is a subsort of the sort NOUN-PHRASE.
The "rules" for composing signs into more complex signs are of two kinds, constructors, which say how to put parts together, and axioms, which place constraints on such constructions. Constructors in this sense are similar to those of abstract syntax (if that concept is already familiar to you). Essentially, constructors are functions that build new signs from (descriptions of) others signs of given sorts, plus possibly some additional parameters. For example, a computer graphics image of a cat may be given as a constructor, with parameters that determine its size, color, and location on the screen; each parameter has its own given sort. For example, cat(red, (800, 250), 2) might produce a red cat at location (800,250), with magnification 2; where the sorts involved are color, location, rational-number, respectively. The arguments of a constructors are the "parts" out of which a given thing constructed using that constructor are actually built, i.e., constructors express the whole/part relationships that are basic to complex signs.
In many examples, some constructors for signs of a given sort are more important than others. For example, a warning popup window is more important than a virtual pet cat. This gives rise to an ordering on the constructors of a given sort, called the priority ordering. In this ordering, there may be a primary constructor, the one constructor (of a given sort) that constructs the most important signs of that sort; there may be one or more secondary constructors, each having priority less than the primary constructor, but greater than any non-primary and non-secondary constructor, with none of these having priority over any other; similarly, there may be one or more tertiary constructors; and so on. This is a partial ordering rather than a total ordering: given two distinct constructors r1 and r2, it is not necessary that either one has priority over the other. For example, the reasoning discourse type  has a primary constructor, AND, which conjoins a number of reasons for the same statement1. There has not been much experimental work in this area, but results of Goguen and Linde  on multimedia instruction about a simple electronic device support this feature.
In addition to constructors, there may be some attributes defined on signs; these are functions or predicates defined on signs of a given sort; for example, a location function will give coordinates for a graphical object (say in number of pixels upward and rightward from the lower lefthand corner of a screen). Similarly, there might be a predicate to tell whether a window is "backgroundable" or not. Another example of an attribute that is a function is COLOR, which may be defined on some sorts of signs. An example of a predicate is HIGHLIGHTED, which may be defined on some other sorts of signs, and may be true or false. Axioms are logical formulae built from constructors, predicates, functions, etc. and used to constrain the set of possible signs; an example is given below.
A fundamental strategy for managing the complexity of non-trivial systems is to have a hierarchy of levels, with each but the lowest level consisting of complex parts constructed from simpler parts at lower (or possibly the same) levels. For example, linguistics distinguishes the levels of phonology (the sounds of a given language), morphology (the smallest repeated compounds of phonemes that have stable meaning), lexicography (words), syntax (phrases and sentences), and discourse (multisentential units), where signs at each level are constructed from others at lower (or the same) levels. A huge, even infinite, number of signs are possible in some systems, including natural languages, due to the recursive nature of rules for combining signs. We add the constraint that signs at a given level n can only be constructed from other signs at levels less than n (and possibly other signs at level n).
The whole/part hierarchical organization for complex signs means that a sign must be considered in the context of the other signs that surround it in space and/or time, and that together with it form a complex sign. Numerous linguistic studies have shown that the context, including the speaker and setting of a given sentence, can be at least as important for meaning as the words that are used. For an extreme example, the sentence "Yes" can be made to mean almost anything by giving an appropriate context. For another example, artificial intelligence has found that contextual cues are essential for recognizing and disambiguating signs in speech understanding and machine vision systems. This corresponds to an important insight of Peirce , not sufficiently emphasized in the literature, that meaning is relational, not just denotational (i.e., functional), and in particular is generally highly dependent on context; this is part of the point of his famous semiotic triangle. In our more technical language, we might say that there may be important constructors that place signs in their context, and that should therefore be considered part of the sign.
Another important insight of Saussure that also seems not to have been sufficiently emphasized, is that sign systems are organized by systematic differences among signs; we can relate this to a famous saying of Gregory Bateson, that "information is a difference that makes a difference." The concepts of sort, attribute, level, constructor, and priority can all be used to specify systematic differences among signs, in the sense that Saussure emphasized.
We now take some first steps towards formalizing these ideas. The syntax for a declaration of a constructor of signs of sort s from signs of sorts s1...sk with parameters p1...pm, which come from some given "data sorts" that are not themselves signs in the system, is as follows:
r : s1 ... sk p1 ... pm -> sWe can use a similar notation for attributes,
location : WINDOW -> PIXEL-PAIRAnd we can indicate subsort relationships with a notation like
subsort NOUN < NOUN-PHRASE
Sorts, constructors and subsorts have the same expressive power as context free grammars, or equivalently, the BNF syntax notation. For example, the constructor r and the subsort relation appear as follows in BNF:
s ::= r(s1, ..., sk, p1, ..., pm) noun-phrase ::= noun
The above discussion is an informal motivation for the main parts of the definition of sign system; it is not a formal definition - for that, see the first definition in [B], which also gives further definitions, many examples, and much more detail. We now give some examples in a bit more detail.
Artificial systems often have the structure of a sign system in a natural way. For a first simple example, we will define a sign system denoted TOD for the time of day in minutes: it has just one sort, TIME; and just two constructors, the constant 0 for midnight, and a unary operation s, where for a time t, s(t) is the next minute; there are no subsorts, data sorts, levels, or priorities, but there is one important axiom,
s1440(t) = t
which basically says that days are 1440 minutes long. The function s is a "successor" function on time, which works like a clock "tick". Howeveer, most real analog clocks have 12 hour cycle, and hence satisfy the axiom
s720(t) = t
For a second example, consider a simple line-oriented display with a 24 line by 80 character screen (the VT100 is like this). The sorts here are character, line, screen. Of these, the lowest hierarchical level is that of characters, the second of lines, the third of screens. Signs at the second level are strings 80 or fewer characters, while signs at the third level are strings of 24 or fewer lines. It is customary to distinguish a number of subsorts of the sort for characters, as shown in the subsort diagram below:
char / \ alphanum special / \ alpha numThere are several ways to give constructors for the VT100 sign system. Perhaps the simplest is to have one constructor for concatenating signs at each level to create lists of signs at that level, constituting signs at the next higher level; thus, lines are lists of characters. There are also some important predicates and functions, such as the LENGTH-LENGTH function for lines, and the NUMERIC predicate for characters. There are two axioms, the first of which says that lines cannot have more than 24 characters, and the second of which says that screens cannot have more than 80 lines; these can be easily expressed in various logics, e.g., first order predicate logic. Let us denote this sign system by W.
Computer graphics signs include characters, squares, lines and circles. Levels are pixels (individual "dots" on the screen), simple figures, and windows (consisting of arbitrary "scenes," which are collections of signs at lower levels, plus other windows); each sign at each level has attributes for location and size; there may also be attributes for color and intensity. The WINDOW constructor can take lower level signs as well as windows, for its arguments, and thus is recursive. The cat constructor that was discussed above can also be considered part of this sign system.
It is easy to define some simple sign systems for texts, TXT for sequences of sequences of characters, and PS for parsed sentences over a simple grammar; see [B] for details.
Sign systems are similar to abstract data types, in that the same information can be represented in a variety of different ways; for example, consider dates, or times, or sports scores. This leads naturally to the idea that representations are mappings between sign systems, which are abstract data types with some extra structure, as discussed in Section 3, and also as illustrated in the UCSD Semiotic Zoo, where exhibits show how some structure was not being properly preserved by some mapping. That interfaces are representations and representations are mappings between semiotic systems is perhaps the most important idea of algebraic semiotics.
You might have expected that the definition of sign system would call for giving some set of signs for each sort; instead, it gives a language for talking about such sets. A logician would say that our sign systems are theories rather than models. The distinction involved is that a theory provides a language, while a model of a theory provides interpretations for the things in the language: sorts are interpreted as sets; constant symbols are interpreted as elements; constructors are interpreted as functions, etc. This allows a lot of flexibility for what can be a model - but we do need to exclude models where two different terms (terms are compositions of constructors) denote the same thing. For example, without this condition, two different times of day could be represented the same way, which is obviously undesirable. This is called the no confusion condition.
Exercise: Notice that the no confusion condition appears to be violated by the 12 hour clock discussed above, and explain why it is not really violated in the usual contexts.
It seems that readers often at first think that basing our formalism on theories rather than models is unnecessarily complex. However, the approach has some significant advantages, the most important of which is that theories in general have many models, and moreover these models may have additional structure that is not called for in the theory; that is, theories are open, and hence accommodate the fact that our understanding is always only partial. (The approaches of Gentner  and Carroll  that were mentioned in Section 1 are model-based.)
A given model of a given sign system will have a specific set of given elements to represent signs, which (by no confusion) should be distinct in any model of that system, but which need not be different from the elements of a model of some other sign system. For example, the different accents of a given language correspond to different models, which nevertheless, in the case of their vowel systems, share a common set of signals. This example shows that the elements of a fixed set of physical signals can serve as signs in multiple ways, by being organized as models of the same sign system in different ways.
One may also notice that some signals are shared by two or more of the Roman, Greek and Cyrillic alphabets, while others are not. This example shows that a physical configuration that is meaningful in one sign system may not be in another, even when they are in the same medium, and that, even if it is meaningful, it may have a different meaning (e.g., consider the token "P"). Thus, semiosis, which is the construction of meaning, occurs in the context of a system of related signs, which is governed by its own rules for construction, recognition, and interpretation. Semiotics as a discipline should be concerned with such systematic structure, rather than with merely comparing individual signs and the settings in which they are found, just as modern biology is based on structures from molecular biology, rather than on the classification schemes of the older descriptive biology.
Note that the signs in a model of a sign system may be expressed using more than one medium at once; for example, TV is an audio-visual mix. But of course a mixture of media may be regarded as a single mixed medium; such media are characterized by relations of simultaneity among some parts, as opposed to pure sequentiality. Also different models of the same sign system may make use of different media or mixtures of media. But you cannot convey any information with a model that has just one element (technically, we may say that its Shannon information content is zero - for example, if Paul Revere had said "One if by land and one if by sea," then a hanging light in the church would convey no information about which of the two options the British soldiers had chosen (although whether or not the light is hanging does convey one bit of information)).
The example of the vowel systems for the accents of a language shows how exactly the same sign system can be realized in different ways, even using exactly the same elements, but in a different way. This emphasizes that it is how elements are used that makes the models different, not the elements themselves. Actually, models of sign systems must be not just sets of elements to represent signs, they must also have the additional structure called for by the given sign system, including its operations, attributes, etc. In particular, the models of a sign system are algebras, in a sense made precise in [B].