From ProofWiki
Jump to navigation Jump to search


A collation is a structured alignment with certain placeholders that underpins the construction of formal languages.

These placeholders may be replaced by elements of an alphabet $\AA$ under consideration.

A collation in $\AA$ is one where all placeholders are replaced by symbols from $\AA$.

For example, if we take $\square$ to denote a placeholder, then $\square\square\square\square\square$ represents the collation "a word of length $5$".

We can see that then the word "sheep" is an instance of the collation "a word of length $5$" in the English alphabet, as is "axiom".

Typical examples of collations encountered in mathematics are words or structured graphics like labeled trees.

Collation System

A key feature of collations is the presence of methods to collate a number of collations into a new one.

A collection of collations, together with a collection of such collation methods may be called a collation system.

For example, words and the method of concatenation.

Unique Readability

Let $\CC$ be a collation system.

Let $\AA$ be an alphabet.

Suppose that for any two collations from $\CC$, $C$ and $C'$, in the alphabet $\AA$, it holds that:

If $C$ and $C'$ are indistinguishable, then $C = C'$.

Then $\CC$ has the unique readability property for $\AA$.


The concept of collation being a very fundamental and abstract one, it is helpful to discuss some examples.

  • Any word in natural language is a collation in the standard alphabet;
  • Any number is a collation in the alphabet of digits;
  • Any sentence is a collation in the alphabet of all words;
  • Any sentence is a collation in the alphabet of letters and punctuation marks;
  • Any movie is a collation in the alphabet of stills;
  • Any Lego construction is a collation in the alphabet of Lego bricks;
  • Any labeled tree is a collation.

We see that unique readability is typically ensured by:

  • Position on the paper (or any other 2D carrier);
  • Position in time;
  • Position in the real world (or any other 3D environment).

Examples from Literature

Bourbaki Assembly

An assembly is a succession of signs written one after another.

Certain signs which are not variables are allowed to be joined in pairs by links, as follows:

$\overbrace {\tau A \Box}^{} A'$

Also see

  • Results about collations can be found here.