# Definition:Collation

## Definition

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 $\mathcal A$ under consideration.

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

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 $\mathcal C$ be a collation system, and let $\mathcal A$ be an alphabet.

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

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

Then $\mathcal C$ has the **unique readability property** for $\mathcal A$.

## Examples

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).