See discussions, stats, and author profiles for this publication at: [Link]

net/publication/285351535

Codes

Article · January 1997

DOI: 10.1007/978-3-642-59136-5_8

CITATIONS READS
93 325

2 authors, including:

Stavros Konstantinidis
Saint Mary's University
96 PUBLICATIONS 960 CITATIONS

SEE PROFILE

All content following this page was uploaded by Stavros Konstantinidis on 04 January 2016.

The user has requested enhancement of the downloaded file.

 1

Codes1
H. Jürgensen, S. Konstantinidis

1. Introduction
Codes are formal languages with special combinatorial and structural prop-
erties which are exploited in information processing or information trans-
mission. In this application, codes serve several different purposes. In the
following discussion we assume the well-known model of information trans-
mission consisting of a source S sending information to a recipient R via a
channel C as illustrated in Fig. 1.1. Before actual transmission, the informa-
tion is encoded using an encoder γ and, before reception, it is decoded using
a decoder δ. During transmission, the encoded information may undergo
changes due to environmental conditions or faults in the channel; the poten-
tial presence of such changes is modelled by a source N of noise. Moreover,
the information may be overheard or even altered during transmission by a
hostile participant F .
In this model, S and R may, but need not be distinct physical objects,
and C may represent any kind of physical channel, a wire, a compact disk,
a computer memory, a nerve connection, a computer program, radio waves
– anything accepting an input and producing an output. In this handbook
chapter we consider only discrete channels which operate in discrete time
steps and which use discrete signals. We represent the signals processed by
a channel as symbols over some alphabet. Hence, we model a channel as
a device which, for input strings – finite, one-sided infinite, or bi-infinite
sequences of symbols –, produces output strings. Input strings are called
messages and output strings are called received messages in the sequel.
The purposes of the encoding γ and the decoding δ include the following:
• translation between the alphabets used by S, C, and R;
• reduction of the effect of noise on C;
• adaptation of the information rates at which S, C, and R operate;

1
We gratefully acknowledge the support of this work by the Natural Sciences
and Engineering Research Council of Canada, Grant OGP0000243. We also thank
colleagues and friends, especially F. Gécseg and K. Salomaa, for their comments
on an earlier version of this chapter.
2 H. Jürgensen and S. Konstantinidis

F
....
......
........
...
.........
........
...

S ................................................ γ ............................................... C ............................................... δ ............................................... R

....
.......
..........
...
...
...
....

Fig. 1.1. The information processing and transmission model.

• data compression;
• information security.
A very basic requirement is that γ and δ operate correctly, that is,2 that
δ(γ(w)) = w for every message w. This assumes that the channel, without
noise and tampering by F , will output w when it gets w as input.3 This
requirement is not sufficient when noise is present or when F might change
messages.
For implementation reasons, γ is usually assumed to work by symbols,
that is, γ acts as a homomorphism,4 mapping the output symbols of S onto
input words of C. The decoding δ, on the other hand, usually cannot work
on a symbol-by-symbol basis. This raises the following issues:
• delay of decoding, that is, how much of an encoded message δ needs to see
before it can issue its first output symbol with certainty;
• delay of synchronization, that is, how much of an encoded message δ needs
to see after an interruption before it can again start decoding correctly.
These issues are very important from the point of view of applications as
they determine the speed at which the system may operate.
In the presence of noise, another set of problems needs to be addressed:
• the presence of errors in a received message needs to be detected;
• some errors in the received message should be corrected.

2
A weaker assumption would be sufficient in general, that is, that δ(γ(w)) be
what S “intends” it to be. However, mathematically, this does not make a signifi-
cant difference.
3
This assumption, while reasonable in most physical situations, can be avoided
as shown in Section 5.
4
Also transducer-based encoding methods are frequently used – for example con-
volution codes –, in particular for certain error correction or data compression
applications; see [99] and [103].
 Codes 3

The noise source N is usually modelled by a stochastic source that, somehow,

influences the behaviour of the channel. Thus, error detection and error
correction can only be expected to be achieved up to a certain probability
threshold. Error detection is mainly a matter for δ to accomplish. Error
correction may also be achieved by δ, but other system components, like
protocols, could be involved as well.
To consider the adaptation of information rates and information compres-
sion, one models S and C as probability spaces [22], [36]. Under appropriate
assumptions about these spaces, quantities like the average information con-
tents of a transmitted symbol can be defined in a physically meaningful way.
Finally, an encoding γ can be used for encryption to make a message
unintelligible for F and to equip it with hidden attributes for δ to detect
tampering with the message by F . Beyond codes5 one also uses transmission
protocols to deal with the threats arising from F .
Given this wide range of requirements, the general theory of codes em-
ploys concepts and tools from quite a few different areas of mathematics,
among them probability and information theory, combinatorics, algebra, and
geometry. In this survey – in the spirit of this handbook – we focus on issues
which arise when codes are considered as formal languages, that is, mainly
on combinatorial issues. Probability theoretic and information theoretic ones
are discussed only briefly to set the stage.
The theory of codes has developed into several nearly unrelated fields:
• information theoretic considerations are used to derive the existence and
general properties of codes regarding information rate and usability on
various channels;
• the theory of error-correcting codes employs a non-probabilistic error model
to design and evaluate codes for various types of channels;
• the theory of variable-length codes6 investigates combinatorial properties
of codes with little regard to their error-correcting properties.
We refer to [22] or [36] as sources regarding the information theoretic aspects
of coding theory. For the theory of error-correcting codes we refer to [99] or
[94]. With very few exceptions, the theory of error-correcting codes concerns
codes in which all code words have the same length. In contrast to this, the
theory of variable-length codes deals with codes the code words of which may
have different lengths, but rarely considers error-correction or error-detection

5
The cryptographic literature has a special meaning for the word code which is
quite different from its meaning in coding theory (see [67], for example); on the
other hand, the notions of encryption in cryptography and encoding in coding and
information theory are nearly identical. Hence, we use encoding to mean both and,
for now, code to mean the system employed.
6
This terminology is quite unfortunate. The lengths of code words in such a code
are not variable as the term might suggest, but they vary.
4 H. Jürgensen and S. Konstantinidis

properties of such codes. We refer to [4] and [123] for the theory of variable-
length codes.
Even with the focus just on language theoretic and combinatorial aspects
of variable-length codes, the field is so wide that we cannot cover everything
in this survey, not even all major aspects. In view of this, we finally decided to
present mostly material that is not readily available in any book on codes. We
intend this survey to complement existing book publications and to interpret
the material in the context of information transmission systems. We hope
to present a unifying view of the field incorporating some of its language
theoretic as well as some of its communication theoretic aspects.
The theory of variable-length codes originated in concrete problems of in-
formation transmission. Its language theoretic branch has taken a direction,
however, which was often guided more by mathematical considerations than
by issues of the application. This is by no means intended to be a criticism of
the work or the results; in fact, some very deep insights about the combina-
torics on words have been obtained as results of research on codes and many
unexpected applications, aside from information transmission, of the theory
of codes have been detected. Whenever appropriate, we emphasize the in-
formation theoretic considerations that motivate some of the constructions.
Also in this respect, this survey will complement the existing literature on
codes.
This handbook chapter is structured as follows: After this introductory
section, we introduce the notation and some basic notions in Section 2. Some
effort is spent to set up a very precise notation for words, languages, and
factorizations of words. For example, we distinguish between word schemata,
instances of word schemata, and words – the latter being equivalence classes
of instances of word schemata. This permits us to give precise meanings
to notions like channel, code, factorization, decoding, synchronization even
when bi-infinite messages are considered and noise must be assumed to be
present on the channel. Of course, for an intuitive understanding of the field,
the reader may just substitute their usual language theoretic counterparts,
as far as they exist; for a completely unambiguous treatment, however, a
formalization like ours is inevitable. In fact, we even omitted a few details
that were not absolutely needed for the presentation in this article.
In Section 3, we then introduce the notions of channel and code. We single
out the class of P-channels as a class defined by a set of physically convincing,
but very general properties. The notions of message, received message, unique
decodability are defined. Moreover, we discuss the decidability of unique
decodability.
In Section 4, we introduce the general notions of error-correction, syn-
chronization, and decoding. For channels permitting insertions, deletions,
and substitutions of symbols it is decidable whether a finite language is error-
correcting for finite messages. The notions of synchronization and decoding
reveal that the properties of P-channels are not restrictive enough to yield
 Codes 5

technically realizable results; additional restrictions are needed which, how-

ever, may be physically significant.
In Section 5, we explain an alternative approach to the notions of error-
correction and decoding. This approach is based on homphonic codes and
leads to another formal channel model. We point out the connections and
discuss the differences.
In Section 6, we explain the underlying scheme by which, in most cases,
natural classes of codes can be defined. The definition method has nothing
whatsoever to do with formal languages, words, or free monoids. It is based
on the purely set theoretic notion of dependence system as proposed in [16].
We review some basic definitions and results of that theory and express the
definition of a large number of classes of codes in this framework. For most
of the classes, we briefly review some of their prominent properties. We pay
particular attention to issues like error-detection and error-correction.
In Section 7, we present an attempt at a systematic understanding of the
relations among the classes of codes introduced up to this point. We expand
the presentation of dependence theory as required and describe general prin-
ciples and properties of constructions of hierarchies of classes of codes. In
this way, we obtain a uniform treatment of many cases that have been dealt
with by special and separate methods so far; moreover, we establish a formal
framework for many more potential cases.
In Section 8, we present results about syntactic monoids of codes. This
complements various book-form presentations on syntactic monoids of the
message sets over codes. The main point in this section is that, under cer-
tain formal conditions, the predicate defining a class of dependence systems
is inherited via syntactic morphisms. In such a case, the properties of the
corresponding independent sets, that is, codes, are directly visible in their
syntactic monoids. In certain situations this can be exploited to decide prop-
erties of codes.
Section 9 focusses on the structure of the decision problem of code prop-
erties. We present two non-equivalent general decision procedures, one based
on syntactic monoids and one based on transducers. We speculate, why these
fail in certain cases and present a survey of known decidability and undecid-
ability results.
In Section 10, we present a summary of many results about maximal
codes; we relate some of these to a general theorem pattern about dependence
systems. A general meta-theorem on the lines suggested does not exist so
far. Using dependence theory, however, we present, a special case of such a
meta-theorem which explains and supersedes many special-case proofs.
In Sections 11 and 12, we turn our attention back to codes for noisy chan-
nels. In Section 11, we focus on solid codes. Such codes have remarkable
synchronization capabilities in the presence of noise. As such they are quite
good at error-detection, but not very good at all at error-correction. We
discuss results concerning their structure and their cost in terms of commu-
6 H. Jürgensen and S. Konstantinidis

nication time. In Section 12, we briefly present codes that can be or are
used for certain kinds of noisy channels. We discuss some basic issues about
modelling noisy channels and the construction of error-correcting codes for
arbitrary noisy channels.
Finally, Section 13 contains a few concluding remarks.
This handbook chapter on codes is not intended to recount the history
of the theory and applications of codes. We cite only work which is directly
relevant to the material presented. We treat the books [4] by Berstel and
Perrin and [123] by Shyr as standard references for a large part of the earlier
results and, in general, do not trace results back to the original authors. In
these books one can usually find the references to the originals. Despite this,
our list of references is quite long and it is still very far from being complete.

2. Notation and basic notions

This section serves two purposes: We introduce the notation used throughout
the handbook chapter, and we review some basic definitions and results.
The symbols Z and N denote the sets of integers and of positive integers,
respectively; let N0 = N ∪ {0} and Nℵ0 = N ∪ {ℵ0 }. The symbol R denotes
the set of real numbers, and R+ denotes the set of positive real numbers.
We denote by |S| the cardinality of a set S. For a set S1 × S2 , the first
and second projections are denoted by π1 and π2 , respectively. If % ⊆ S1 × S2
and s1 ∈ S1 , then %(s1 ) = {s2 | s2 ∈ S2 , (s1 , s2 ) ∈ %}. By 2S2 we denote the
set of all subsets of S2 , and 2S6=2∅ is the set of all non-empty subsets of S2 .
Let σ be a mapping of S1 into 2S2 . Whenever convenient, we identify σ with
the relation {(s1 , s2 ) | s1 ∈ S1 , s2 ∈ S2 , s2 ∈ σ(s1 )}. If τ is an equivalence
relation on a set S, then a cross section of τ is a subset of S containing
exactly one element of each equivalence class with respect to τ .
For a set S and n ∈ Nℵ0 , Subn S denotes the set of all subsets of S of
cardinality strictly less than n. Thus, Sub1 S = {∅} and Subℵ0 S is the set
of all finite subsets of S.
For n ∈ N0 , let n = {0, 1, . . . , n − 1}; thus, 0 = ∅ and 1 = {0}. Let
ω = N0 , −ω = {−n | n ∈ N0 }, and ζ = ω ∪ −ω = Z. We define

nω o
0 < 1 < 2 < ··· < < ζ.
−ω

Let I = {n | n ∈ N0 } ∪ {−ω, ω, ζ}. In this handbook chapter, a set I is said

to be an index set if I ∈ I. For index sets I and J, let

{i | i ∈ N0 , i < n + m}, if I = n, J = m with n, m ∈ N0 ,



ω, if I = n, J = ω with n ∈ N0 ,

I +J =
 −ω,
 if I = −ω, J = n with n ∈ N0 ,
ζ, if I = −ω, J = ω.
 Codes 7

The definition of addition could be extended to all pairs of symbols in I;

however, we do not need it for any cases beyond these.7 For an index set I
and an integer n let n + I = I + n = {n + i | i ∈ I}.
A mapping ψ of an index set I into an index set J is an index mapping
if it is injective and order-preserving and if the image of I is a convex subset
of J, that is, ψ(i) < j < ψ(i0 ) for i, i0 ∈ I and j ∈ J implies that j = ψ(i00 )
for some i00 ∈ I.
An alphabet is a non-empty set of symbols. In this section, let X be an
arbitrary, but fixed alphabet.
A word schema w over X is a mapping of an index set Iw into X. A word
schema is specified by its index set Iw and the symbols w(i) ∈ X for i ∈ Iw .
A word schema w is finite if |Iw | is finite, that is Iw = n for some n ∈ N0
and n = |Iw | is the length of w denoted by |w|. A word schema w is said to
be right-infinite if Iw = ω and left-infinite if Iw = −ω. A word schema w is
said to be bi-infinite if Iw = ζ. An infinite word schema is a word schema
which is right-infinite or left-infinite or bi-infinite.
Two word schemata w and v over X are said to be equivalent, w ∼ v, if
there is a j ∈ Z such that j + Iw = Iv and w(i) = v(j + i) for all i ∈ Iw .
Suppose w and v are equivalent word schemata. If Iw < ζ then Iv = Iw
and v = w. If Iw = ζ then Iv = ζ and it is possible that w(i) 6= v(i) for some
i ∈ ζ, that is, w 6= v.
Let w be a word schema over X. An instance of w is a mapping [[w, n]]
of n + Iw into X for some n ∈ Z such that [[w, n]](i + n) = w(i) for all i ∈ Iw .
In particular, [[w, 0]] = w. The equivalence ∼ of word schemata induces an
equivalence of instances of word schemata: Let w and v be word schemata
over X and n, m ∈ Z; the instances [[w, n]] and [[v, m]] are said to be equivalent,
[[w, n]] ≈ [[v, m]], if w ∼ v. Some examples of equivalent instances of word
schemata are shown in Fig. 2.1. All instances of a given word schema are
equivalent. Two word schemata w and v either have no instances in common
or the same instances.
A word over X is an equivalence class of instances of word schemata. In-
tuitively, a word schema describes a sequence of symbols fixing some starting
point 0. An instance of a word schema is obtained by shifting the starting
point. A word is the sequence itself without reference to the starting point.
In the context of information transmission, the starting point represents the
time at which the symbol at this point is being sent.
• For every word w, let S(w) be an arbitrary but fixed word schema8 the
instances of which belong to w.

7
The similarity with ordinal numbers is intended.
8
By the definition of word schemata, there is no arbitrariness in the selection of
S(w) except when w is bi-infinite.
8 H. Jürgensen and S. Konstantinidis
8
< Iw = {0,
 1, 2, 3} indices for [[w, 5]] 5 6 7 8
(a) 1, if i = 1, symbols 0 1 0 0
: w(i) =
0, if i 6= 1 indices for [[w, −10]] −10 −9 −8 −7

( Iw = ω
 indices for [[w, −2]] −2 −1 0 1 ...
(b) 1, if i = 1, symbols 0 1 0 0 ···
w(i) =
0, if i =
6 1 indices for [[w, 0]] 0 1 2 3 ...

8
< Iw = ζ indices for [[w, −2]] ... −4 −3 −2 −1 ...
(c) 1, if i = −1, symbols ··· 0 1 0 0 ···
: w(i) = 0, if i =
6 1 indices for [[w, 0]] ... −2 −1 0 1 ...

Fig. 2.1. Examples of equivalent instances of word schemata: (a) finite word
schema; (b) right-infinite word schema; (c) bi-infinite word schema.

• For a word w let I(w) be the set of all instances9 of S(w); similarly, for a
word schema v, let I(v) be the set of all instances of v; moreover, let v be
the equivalence class of all instances of v.
• For any instance u of a word schema, let S(u) be an arbitrary but fixed
word schema with u ∈ I(S(u)) such that, if u and v are instances of word
schemata and u ≈ v, then S(u) = S(v).
This seemingly cumbersome distinction between words, word schemata, and
instances of word schemata is needed in some cases in the sequel to avoid
ambiguity. When no ambiguity is possible in the given context, we just use
the term word. In several situations, however, this distinction is essential to
make statements precise.
Consider word schemata w and v. Their concatenation wv is defined if
and only if Iw + Iv is defined and, in this case,

w(i), if Iw = n for some n ∈ N0 and i ∈ n,



v(i − n), if Iw = n for some n ∈ N0 and i ≥ n,




v(i + n − 1), if Iw = −ω, Iv = n for some n ∈ N0 and i > −n,

wv(i) =

 w(i + n), if Iw = −ω, Iv = n for some n ∈ N0 and i ≤ −n,
 w(i + 1), if Iw = −ω, Iv = ω and i < 0,



v(i), if Iw = −ω, Iv = ω and i ≥ 0,

for i ∈ Iwv = Iw + Iv . When using concatenation, we implicitly assume that

it is defined.
Consider two instances [[w, n]] and [[v, m]] of word schemata such that wv
is defined. Then any two instances of the word schema wv are equivalent.
The concatenation of word schemata corresponds to the usual definition of
concatenation of words.

9
By definition, w itself is the set of all instances of S(w); we introduce this
notation, albeit redundant, to avoid confusion.
 Codes 9

Let S be the set of symbols

I ∪ {∗, ¨} ∪ {≤I | I ∈ I} ∪ {<I | I ∈ I}.

For I ∈ I, let X I be the set of all words w such that IS(w) = I; let X <I =
≤I
J
= X <I ∪ X I ; finally, let X ∗ = X <ω , X ¨ = X ≤ζ , and let
S
J<I X and X
∗
X = X \ {λ} where λ denotes the empty word,10 that is, the word with
+

IS(λ) = ∅. With this notation, X ∗ , X + and X ω get their usual meanings in

language theory; the set X ≤ω is often denoted by X ∞ . For η ∈ S, w is an
η-word schema if w ∈ X η ; an η-language is a set of η-words. In the rest of
this handbook chapter, word means ¨-word and language means ¨-language.
Many statements about words or languages remain true if one reads the
words from right to left instead of from left to right and if one exchanges ω
and −ω. We refer to this fact as duality and use it frequently.
Let Y ⊆ S(X ¨ ) and let ϕ be a mapping of an index set Iϕ into Y . Assume
that, for every j ∈ Iϕ , if j + 1 ∈ Iϕ then ϕ(j)ϕ(j + 1) is defined. Let [ϕ] be
the word schema defined by [ϕ](i) = ϕ(j)(k) where j ∈ Iϕ , k ∈ Iϕ(j) , and
where j and k are determined by
 j−1
P
|ϕ(l)|, if i ≥ 0 and Iϕ = ζ or Iϕ ≤ ω,





 l=0
−1

 P
i−k = − |ϕ(l)|, if i < 0 and Iϕ = ζ,

 l=j
0


 P
1 −

 |ϕ(l)|, if i ≤ 0 and Iϕ = −ω.
l=j

The index set of [ϕ] is the set of i for which such j and k exist. Intuitively,
[ϕ] is the word schema over X which is obtained as the concatenation of the
images of ϕ in the given order such that the occurrence of ϕ(0) starts at
position 0. We illustrate the typical situations in Fig. 2.2.
Definition 2.1 For y ∈ S(X ¨ ) and Y ⊆ S(X ¨ ), a factorization11 of y
over Y is a mapping ϕ of an index set Iϕ into Y such that [ϕ] ∼ y. Two
factorizations ϕ and ϕ0 of y over Y are said to be equivalent, ϕ ∼ ϕ0 , if there
is an integer n such that n + Iϕ = Iϕ0 and ϕ(i) = ϕ0 (n + i) for all i ∈ Iϕ .

Remark 2.1 Consider a word schema y and two equivalent factorizations ϕ

and ϕ0 of y over Y . If Iϕ < ζ then ϕ = ϕ0 .

10
In the sequel we use λ also to denote the empty word schema. The precise
meaning will be clear from the context.
11
For simplification we often speak of factorizations over a set K of words rather
than word schemata; in such cases, it is implied that the factorization is over S(K).
10 H. Jürgensen and S. Konstantinidis

ϕ(j 0 )(0) ϕ(j)(0)

ϕ(j 0 )(k0 ) . . . ϕ(−1)(0). . . ϕ(0)(0) . . . ϕ(1)(0) . . . ϕ(j)(k)
↓ ↓ ↓ ↓ ↓ ↓ ↓
(a) . . . .........................•.........................•.............................................................................•...................................................•...................................................•.............................................................................•.........................•....................... . . .
↑ ↑ ↑ ↑ ↑ ↑ ↑
i0 −|ϕ(−1)| 0 |ϕ(0)| j−1
i
−1
P P
− |ϕ(l)| |ϕ(l)|
l=j 0 l=0

ϕ(j)(0)
ϕ(j)(k) . . . ϕ(0)(0) . . .
↓ ↓ ↓ ↓
(b) . . . .........................•.........................•.............................................................................•..................................................•
↑ ↑ ↑ ↑
i 1 − |ϕ(0)| 0
0
P
1− |ϕ(l)|
l=j

Fig. 2.2. The typical arrangement of symbols in [ϕ]: (a) the cases of Iϕ = ζ or
Iϕ ≤ ω, shown for i ≥ 0 and i0 < 0; (b) the case of Iϕ = −ω. In both cases the
upper row shows the symbols; the lower row shows the indices.

Note that a factorization ϕ of y ∈ S(X ¨ ) over Y ⊆ S(X ¨ ) is itself a

word schema over the alphabet Y . With this intuition, the equivalence of
factorizations coincides with the equivalence of word schemata. Moreover,
for any index set I, Y I is the set of all word schemata12 over X having a
factorization ϕ over Y with Iϕ = I.
If v ∈ X + then, v ω denotes the unique ω-word representing {S(v)}ω . The
words v n for n ∈ N0 , v −ω , and v ζ are defined analogously.
A word w ∈ X + is said to be primitive if w = un for u ∈ X + and n ∈ N
implies n = 1. The root of a word w ∈ √ X + is the unique primitive word u
n
such that w = u√ for some n ∈ √ N. By w we denote the root of w. For a
set L ⊆ X + , let L be√the set √ w | w ∈ L}. For any words v, w ∈ X , let
{ +

v ∼ √ w if and only if v = w.
As mentioned before, we use a simplified and more intuitive notation when
there is no risk of ambiguity. Thus, with X = {0, 1}, the word w = 0010
would be used to describe the word schema w with Iw = 4, w(0) = w(1) =
w(3) = 0, and w(2) = 1. Similarly, we write v = · · · 010101 to denote the
word schema v with Iv = −ω, v(0) = v(−2) = v(−4) = 1, v(−1) = v(−3) =
v(−5) = 0, and, presumably, v(−2i) = 1, v(−2i − 1) = 0 for all i ∈ N0 .
The reverse notation is used for word schemata in S(X ω ). Even in the case
of word schemata in S(X ζ ), we sometimes use this simplified notation; for
example u ∈ S(X ζ ) with u(2i) = 1 and u(2i − 1) = 0 may just be written as
u = · · · 010101010 · · · when the actual values of the indices are not relevant.
Moreover, as often done in the literature, we indicate factors by enclosing
them in parentheses. For example, factorizations of u over K = {01, 10} can

12
When n ∈ N0 , we usually write Y n instead of Y n .
 Codes 11

be described by

u = · · · (01)(01)(01)(01)(0 · · · = · · · 0)(10)(10)(10)(10) · · · .

Strictly speaking, this notation only describes equivalence classes of factor-

izations.
Example 2.1 Consider the alphabet X = {0, 1} and the set Y = {010}. More
precisely, Y is the singleton set consisting of the word schema w with I w = 3,
w(0) = w(2) = 0, and w(1) = 1. Let ϕ be the mapping of Iϕ = ζ into Y with
ϕ(j) = w for all j ∈ ζ (there is only this mapping). Then
½
0, if i or i − 2 is divisible by 3,
[ϕ](i) =
1, if i − 1 is divisible by 3.

Let v = [ϕ] and Y 0 = {w, w0 } where w 0 = ww, that is, Iw0 = 6, w0 (0) =
w0 (2) = w0 (3) = w0 (5) = 0, and w 0 (1) = w0 (4) = 1. Then v has infinitely
many non-equivalent factorizations over Y 0 . For example, in addition to ϕ,
also ϕ0 with Iϕ0 = ζ, ϕ0 (2i) = w 0 , and ϕ0 (2i+1) = w for i ∈ ζ is a factorization
of v over Y 0 . Fig. 2.3 illustrates this situation.

factorization ϕ ... ϕ(−1) ϕ(0) ϕ(1) ϕ(2) ...

instances . . . [[ϕ(−1), −3]] [[ϕ(0), 0]] [[ϕ(1), 3]] [[ϕ(2), 6]] ...
z }| { z }| { z }| { z }| {
word schema [ϕ] ... 0 1 0 0 1 0 0 1 0 0 1 0 ...
indices . . . −3 −2 −1 0 1 2 3 4 5 6 7 8 ...
| {z } | {z } | {z }
instances . . . [[ϕ0 (−1), −3]] [[ϕ0 (0), 0]] [[ϕ0 (1), 6]] ...
factorization ϕ0 ... ϕ0 (−1) ϕ0 (0) ϕ0 (1) ...

Fig. 2.3. The word schema [ϕ] for ϕ, w, ϕ0 and w0 as in Example 2.1.

Consider w ∈ S(X ≤ω ) and u ∈ S(X ∗ ). The word schema u is said to be

a prefix of w if, for ψ the identity mapping on Iu , one has [wψ] = u; it is
a proper prefix if 0 < Iu < Iw . Let Pref(w)λ and Pref(w) denote the sets
of prefixes and of proper prefixes, respectively. By duality, one defines the
notion of suffix of a word schema w ∈ S(X ≤−ω ).
Consider w ∈ S(X ≤ζ ) and u ∈ S(X ∗ ). The word schema u is an infix of
w if there is an index mapping ψ of Iu into Iw such that [wψ] = u; it is a
proper infix of w if 0 < Iu < Iw .
The intuition leading to these definitions of prefix, suffix, and infix is
illustrated in Fig. 2.4. Note that every prefix and every suffix is an infix.
We assume that the reader is familiar with certain basic notions of for-
mal language theory like finite automaton, generalized sequential machine,
various kinds of acceptors, grammar, regular language, context-free language,
linear language, decidability. If required, definitions can be found in the
corresponding chapters of this handbook.
12 H. Jürgensen and S. Konstantinidis

u
(a)
w

u
(b)
w

u
(c)
w
Fig. 2.4. Illustration of prefix, suffix, and infix: (a) u is a prefix of w; (b) u is a
suffix of w; (c) u is an infix of w.

For the rest of this handbook chapter, we assume that X is an arbitrary,

but fixed finite alphabet with |X| > 1. Moreover, in examples we usually as-
sume without special mention that the symbols 0 and 1 are distinct elements
of X.

3. Channels and codes

In modelling a channel we describe its typical input-output behaviour. In
information theory this usually involves probabilities, that is, the conditional
probabilities of outputs given certain inputs. In the theory of codes the
abstraction usually goes even further: one models the reasonably likely be-
haviour only, and this behaviour is modelled non-deterministically. We use
the latter approach.
Definition 3.1 A channel (over X) is a binary relation on I(X ¨ ). A channel
γ is said to be stationary if, for all y, y 0 ∈ S(X ¨ ) and for all n, n0 ∈ Z, one
has ([[y 0 , n0 ]], [[y, n]]) ∈ γ if and only if ([[y 0 , n0 − n]], [[y, 0]]) ∈ γ.
If γ is a channel over X then we interpret (y 0 , y) ∈ γ to mean that, upon
input y, the channel could output y 0 . To suggest this interpretation we write
(y 0 | y) instead of (y 0 , y) in analogy with the notation used for conditional
probabilities.
For y ∈ S(X ¨ ), let

hyiγ = y 0 ∈ S(X ¨ ) | ∃n, n0 ∈ Z ([[y 0 , n0 ]] | [[y, n]]) ∈ γ ,

© ¡ ¢ª

that is, hyiγ is the set of word schemata that can be obtained as output of
γ when y is used as the input. For Y ⊆ S(X ¨ ), let
[
hY iγ = hyiγ .
y∈Y

Thus hY iγ is the set of all possible outputs of γ when word schemata in Y

are used as inputs.
 Codes 13

For example, if y = [[w, n]], y 0 = [[w0 , m]] with w, w 0 ∈ S(X ∗ ) then (y 0 |

y) ∈ γ means the following: if w(0), w(1), . . . , w(|w| − 1) are the inputs of γ
at times n, n + 1, . . . , n + |w| − 1 then, at times m, m + 1, . . . , m + |w 0 | − 1,
the output symbols can be w 0 (0), w0 (1), . . . , w 0 (|w0 | − 1).
Stationarity means that the absolute time is not important. Thus, if [[γ, k]]
is the channel given by
n ¯ o
[[γ, k]] = ([[w0 , n0 ]] | [[w, n]]) ¯ ([[w0 , n0 − k]] | [[w, n − k]]) ∈ γ
¯

for k ∈ Z, then γ is stationary if and only if γ = [[γ, k]] for all k ∈ Z.

Definition 3.2 Let γ be a stationary channel over X, let Y ⊆ S(X + ),
Y 0 = hY iγ , w, w0 ∈ S(X ¨ ), and let ϕ be a factorization of w over Y . A
factorization ϕ0 of w0 ∈ hwiγ over Y 0 is said to be γ-admissible for ϕ if
Iϕ = Iϕ0 and, for all n, n0 ∈ Z such that ([[w 0 , n0 ]] | [[w, n]]) ∈ γ and for
every non-empty index set I and every index mapping ψ of I into Iϕ , one
has ([[[ϕ0 ψ], n0 ]] | [[[ϕψ], n]]) ∈ γ.
Definition 3.1 seems to be general enough to model most discrete physical
channels.13 In fact, most physical channels seem to satisfy the following
additional conditions:
(P0 ) A channel preserves finiteness and the type of infiniteness, that is, if
y 0 ∈ hyiγ and y ∈ S(X η ) for η ∈ {∗, ω, −ω, ζ} then y 0 ∈ S(X η ).
(P1 ) Input factorizations have corresponding factorizations of the output,
that is, if y 0 ∈ hyiγ and ϕ is a factorization of y over a subset Y of
S(π2 (γ)) ∩ S(X + ) with Iϕ 6= ∅ then there is a factorization of y 0 over
hY iγ which is γ-admissible for ϕ.
(P2 ) Error-freeness does not depend on the context, that is,

if ([[v 0 , n0 ]] | [[v, n]]) ∈ γ then ([[uv 0 w, n0 ]] | [[uvw, n]]) ∈ γ

for all u, w ∈ S(π2 (γ)) with [[uvw, n]] ∈ π2 (γ).

(P3 ) Empty input can always result in empty output, that is,

([[λ, n0 ]] | [[λ, n]]) ∈ γ

for all n, n0 ∈ Z.
The conditions P0 –P3 correspond, roughly, to the following physical assump-
tions: Infinite time periods do not exist, that is, for a message of which we
don’t know the beginning or the end or both, a channel cannot provide that
information; on the other hand, if a message has a definite beginning or a

13
Physical channels sometimes have different alphabets for input and output.
Modelling this is straightforward, but not necessary in the context of this handbook
chapter.
14 H. Jürgensen and S. Konstantinidis

definite end then the channel cannot hide these forever. The noise in a chan-
nel is a property of the channel and not of the messages – this is similar to
the notion of additive noise in information theory. Error-free information
transmission is always possible. If there is no input, then it is always possible
that there is no corresponding output, regardless of the delay. While most
physical channels will have these properties, channels with memory might
violate P2 .
On the other hand, conditions P0 –P3 are really very weak. For instance,
in P2 , if ([[v 0 , n0 ]] | [[v, n]]) ∈ γ then ([[uv 0 w, n0 ]] | [[uvw, n]]) ∈ γ for all
u, w ∈ S(X ¨ ) with [[uvw, n]] ∈ π2 (γ), but it is not guaranteed that the factor-
ization (u)(v 0 )(w) is γ-admissible for the factorization (u)(v)(w). Similarly,
if (u0 )(v 0 w0 ) and (v 0 )(w0 ) are γ-admissible factorizations of u0 v 0 w0 and v 0 w0 ,
respectively, for (u)(vw) and (v)(w), respectively, then one cannot conclude
that (u0 )(v 0 )(w0 ) is a γ-admissible factorization for (u)(v)(w). This situation
may seem rather unnatural. It cannot, however, be avoided in general as it
permits one to model the case when the noise may depend on the message.
Classical error models assume that message and noise are statistically inde-
pendent; for certain types of modern information transmission media this
assumption seems to be not quite adequate.

Definition 3.3 A P-channel is a stationary channel γ with π2 (γ) = I(X ¨ )

which satisfies P0 , P1 , P2 , and P3 .

The noiseless channel {(y | y) | y ∈ I(X ¨ )} is a P-channel. A channel,

which changes, inserts or deletes up to m symbols in every L consecutive
symbols is an example of a noisy P-channel.
In the presence of such errors one cannot, in general, assume that the
output resulting from an input sent at time n is received at time n or at
least, at time n + k for some fixed k ∈ Z. For example, if the channel γ
could insert or delete 1 symbol in every 3 consecutive symbols, then the
input 0010110101101 sent at times 0, 1, . . . , 12 could result in the output
0101011011001 received at times 1, 2, . . . , 13 as shown in Fig. 3.1. Thus,
while it is sometimes convenient to think of the indices in terms of time, this
interpretation can be quite misleading when taken literally. Time should not
be interpreted as physical time in this context. In the case of the channel
with insertions and deletions, if ([[w 0 , n0 ]] | [[w, n]]) ∈ γ, then also ([[w 0 , n0 + k]] |
[[w, n]]) ∈ γ for any k ∈ Z.
Definition 3.2 and the conditions P1 , P2 , and P3 are formulated in such a
way as to take these difficulties into account. For example, in P1 , the input
and output factorizations may not have the same factorization points.
Given a channel, a code needs to be found which guarantees14 that any
message can be unequivocally recovered from the corresponding channel out-
put.

14
Strictly speaking, with high enough probability.
 Codes 15

input times: 0 1 2 3 4 5 6 7 8 9 10 11 12
input word 0 0 1 0 1 1 0 1 0 1 1 0 1
output word 0 1 0 1 0 1 1 0 1 1 0 0 1
output times: 1 2 3 4 5 6 7 8 9 10 11 12 13
Fig. 3.1. Timing of channel inputs and outputs in the presence of insertions and
deletions.

Let η ∈ {∗, ω, −ω, ζ, ≤ω, ≤−ω, ≤ζ} and K ⊆ X + . An η-message over K

is a word schema in S(K η ).
Definition 3.4 A language K is uniquely η-decodable if every η-message
over K has only a single factorization over S(K), up to equivalence of fac-
torizations.
For a stationary channel γ, a γ-received η-message (over K) is a word
schema w 0 such that ([[w 0 , n0 ]] | [[w, 0]]) ∈ γ for some η-message w over K
and some n0 ∈ Z. For an η-message w over K, hwiγ is the set of γ-received
η-messages resulting from input w.
Definition 3.5 A language K is an η-code if K ⊆ X + and K is uniquely
η-decodable.
Usually, the term code means ∗-code in the literature on codes, and this is
also how we use this term in the rest of this handbook chapter. On the other
hand, we often use the terms15 message and received message in the generic
sense η-message and γ-received η-message for some implied, but unspecified
γ and η. For η as above, let Kη be the class of η-codes.
Example 3.1 We illustrate the concepts with a few examples:
(1) The language K = {0, 01, 10} is not a code, not even a ∗-code as the mes-
sage 010 has two non-equivalent factorizations over K: 010 = (0)(10) =
(01)(0).
(2) A language K such that K ⊆ X n for some n ∈ N is called a uniform code
or a block code of (block) length n. A uniform code K of length n is full if
K = X n . Uniform codes are ω-codes and (−ω)-codes, but not necessarily
ζ-codes. For example, consider K = {01, 10}. Then the bi-infinite word
· · · 010101010 · · · has two non-equivalent factorizations over K, that is,

· · · 010101010 · · · = · · · (01)(01)(01)(01)(0 · · ·
= · · · 0)(10)(10)(10)(10) · · · .

15
The terminology and notation for codes in the context of infinite messages seems
to be still evolving. In [21] two kinds of codes are condidered for bi-infinite words,
biω-codes and Z-codes. The former are our ζ-codes. The latter require unique
factorizations, and not just unique factorizations up to equivalence. As already
noted in [21], the notion of Z-code is not really natural in the context of information
processing.
16 H. Jürgensen and S. Konstantinidis

(3) The language K = {101, 01} is an ω-code. If w is an ω-message over K

then the unique factorization of w into word schemata u0 , u1 , . . . ∈ S(K)
can be determined as follows: Let w0 = w. For i ≥ 0, let
½
101, if wi starts with 1,
ui =
01, if wi starts with 0,

and let wi+1 be the ω-word schema satisfying wi = ui wi+1 . In a similar

way one verifies that K is also a (−ω)-code.
This language K is even a ζ-code. To see this, let v be some ζ-
message over K. If v(i) 6= v(i + 1) for all i ∈ ζ then 101 cannot occur in
any factorization of v over K as there is no word ending with 0 in K. If
v(i) = v(i + 1) for some i ∈ ζ then v(i) = 1. The unique factorization ϕ
of v over K is determined as follows: Let ψ1 be the index mapping of ω
into ζ with ψ1 (0) = i + 1 and let ψ2 be the index mapping of −ω into ζ
with ψ2 (0) = i. Let ϕ1 and ϕ2 be the unique factorizations of [vψ1 ] and
[vψ2 ], respectively, over K. Let
½
ϕ1 (j), if j ≥ 0,
ϕ(j) =
ϕ2 (j + 1), if j < 0,

for all j ∈ ζ. Then [ϕ] = [ϕ2 ][ϕ1 ] and [ϕ](l) = v(l + i + 1) for all l ∈ ζ.
(4) The language K = {0, 01, 11} is a ∗-code and even a (−ω)-code, but not
an ω-code because of (0)(11)ω = (01)(11)ω .
The η-codes, for η ∈ {∗, −ω, ω, ζ} form a proper hierarchy (see [21], [128],
and [20], for example).
Proposition 3.1 The following proper inclusions obtain:
n ω o
K
Kζ ( ( K∗ .
K−ω

Proof: First consider K ∈ Kζ , let w be a word schema with Iw = ω, and let

ϕ1 and ϕ2 be factorizations of w over K. Because of Remark 2.1, we need to
show that ϕ1 = ϕ2 . Let v ∈ S(K). Define mappings ψ1 and ψ2 of ζ into K
by ½ ½
ϕ1 (i), if i ≥ 0, ϕ2 (i), if i ≥ 0,
ψ1 (i) = and ψ2 (i) =
v, if i < 0, v if i < 0,
for i ∈ ζ. Thus, ψ1 and ψ2 are factorizations of [ψ1 ] = [ψ2 ] over K and,
therefore, Iψ1 = Iψ2 and ψ1 (i) = ψ2 (j + i) for some j ∈ Z and all i ∈ ζ.
If j = 0 then ψ1 = ψ2 , hence ϕ1 = ϕ2 . Therefore, suppose j 6= 0. Without
loss of generality, we may assume that j > 0. The situation is illustrated in
Fig. 3.2. Thus, w = v j w and, by induction, w = v jn w for all n ∈ N, hence
w = (v j )ω = v ω . Thus, as v ∈ S(K) and K ∈ Kζ , ψ1 (i) = ψ2 (i) = v for all
i ∈ ζ, hence ϕ1 (i) = ϕ2 (i) = v for all i ∈ ω.
 Codes 17

This proves the inclusion Kζ ⊆ Kω . The inclusion Kζ ⊆ K−ω follows by

duality. The inclusion is proper by Example 3.1(2).
To prove that Kω ⊆ K∗ consider K ∈ Kω and a word schema w ∈
S(K ∗ ). Suppose, w has two non-equivalent factorizations over K. Let v ∈
S(K). Then also the word schema wv ω has two nonequivalent factorizations,
a contradiction.
This proves that Kω ⊆ K∗ . The inclusion is proper by Example 3.1(4).
The inclusion K−ω ( K∗ follows by duality. ¤

z w
}| {
... v v ... v ϕ1 (0) ϕ1 (1) ϕ1 (2) ...
... v ϕ2 (0) ... ϕ2 (j − 1) ϕ2 (j) ϕ2 (j + 1) ϕ2 (j + 2) . . .
| {z }
w

Fig. 3.2. Factorizations in the proof of Proposition 3.1, K ζ ⊆ Kω .

A detailed study of the relation between various classes of η-codes for

η ≤ ω is conducted in [128] and [20].16 The following result distinguishes
between ∗-codes and ω-codes.

Theorem 3.1 [20] Let K ⊆ X + . The following conditions on K are equiva-

lent:
(a) K is a ∗-code.
(b) For every u ∈ K + , uω has a unique factorization over K.
(c) For every u ∈ X + with uω ∈ K ω , uω has only finitely many different
factorizations over K.
(d) For every u ∈ X ∗ and v ∈ X + with uv ω ∈ K ω , uv ω has only finitely
many different factorizations over K.

For a given language K ⊆ X + it can sometimes be quite difficult to

determine whether K is an η-code. For the case of K being a finite language
and η = ∗, an algorithm to solve this problem was first given in [115]. An
algorithm to solve this problem for a regular language K can be found in [4],
for example. This result was extended to η = ω by [20] and to η = ζ by [21].
For a complexity theoretic analysis see [88].

Theorem 3.2 Let η ∈ {∗, −ω, ω, ζ}. The following question is decidable:
Given a deterministic finite automaton accepting a language K ⊆ X + , is K
an η-code?

16
In [128], ω-codes are referred to as ifl-codes.
18 H. Jürgensen and S. Konstantinidis

Proofs of Theorem 3.2 rely on two main ideas: If a message has two
distinct factorizations over K then there are words in K which can be made
to overlap each other; when K is regular the possible sequences of overlaps
have certain periodicity properties.
We illustrate the concept of overlap by a small example. Consider a lan-
guage K ⊆ X + and a ∗-message w having two non-equivalent factorizations
ϕ1 and ϕ2 over K. The typical situation is shown in Fig. 3.3. There the
word schemata u0 , u1 , u2 , u3 , v0 , v1 , v2 are assumed to be elements of S(K).
The word schema u0 is proper prefix of v0 ; the rest of v0 is a proper prefix
of u1 ; the rest of u1 is a prefix of v1 ; u2 is an infix of v1 ; the rest of v1 is a
prefix of u3 ; the rest of u3 is equal to v2 .

u0 u1 u2 u3
v0 v1 v2
Fig. 3.3. A finite word schema with two distinct factorizations.

Thus, there are two typical situations:

(1) An instance of a word schema u ∈ S(K) is an infix of another word
schema v ∈ S(K). In Section 6 below, we introduce the class of infix
codes. A language K ⊆ X + is an infix code if and only if there are no
two distinct word schemata in K such that one is an infix of the other.
(2) The end of an instance of a word schema u ∈ S(K) overlaps the beginning
of a word schema v ∈ S(K), where u and v need not be distinct. A class
of infix codes for which such overlaps are explicitly excluded is defined in
Section 6 and analysed in greater detail in Section 11, the class of solid
codes.
These two situations arise in many proofs in coding theory. Several formal-
izations of the notion of overlap exist in the literature, mainly developed in
the context or for the purpose of proving parts of Theorem 3.2 and related re-
sults.17 A definition of overlaps and chains of overlaps that is also applicable
in the case of decoding for noisy channels is given in [70].
In Theorem 3.2, the assumption that K be regular is quite important. For
context-free and even for linear K it is, in general, even undecidable whether
K is a ∗-code.
Theorem 3.3 There is no algorithm which, given a linear grammar G, al-
ways decides whether the language generated by G is a ∗-code.
We could not find a reference to this result which we believe to have seen
proved some twenty years ago. The work in [35] is related to this problem to
some extent. The following proof is due to S. Yu [145].

17
See [4], [110] (reprinted in [41]), [40], [12], [127], [74], [78], [76], and the work
cited there.
 Codes 19

Proof: Let X be an alphabet and let (U, V ) be an instance of Post’s Corre-

spondence Problem, where
U = (u0 , u1 , . . . , un−1 ) and V = (v0 , v1 , . . . , vn−1 )
for some n ∈ N and u0 , u1 , . . . , un−1 , v0 , v1 , . . . , vn−1 ∈ X ∗ . A solution to
(U, V ) is a pair (m, I) where m ∈ N and I is an m-tuple of integers, I =
(i0 , i1 , . . . , im−1 ), such that
ij ∈ n for j ∈ m and ui0 ui1 · · · uim−1 = vi0 vi1 · · · vim−1 .
Without loss of generality, we may assume that the symbols 0, 1, #, $, and c/
are not in X. Let Y = X ∪ {0, 1, #, $, c/}. For any positive integer i, let β(i)
denote the shortest binary representation of i.
Consider the linear grammar G defined as follows: The terminal alphabet
of G is Y . The non-terminal alphabet consists of the symbols S, TU , and TV
with S the start symbol. The rules are
S → β(i)/cTU ui $, S → β(i)/cui $,
S → β(i)/cTV vi $#, S → β(i)/cvi $#, S → #,
TU → β(i)/cTU ui , TU → β(i)/cui , TV → β(i)/cTV vi , TV → β(i)/cvi
for i ∈ n. Let K be the language generated by G. Then K = {#} ∪ KU ∪ KV
where KU and KV are languages consisting precisely of all the words
β(im−1 )/cβ(im−2 )/c · · · β(i0 )/cui0 · · · uim−2 uim−1 $
and
β(im−1 )/cβ(im−2 )/c · · · β(i0 )/cvi0 · · · vim−2 vim−1 $#,
respectively, for all m ∈ N and all i0 , . . . , im−1 ∈ n.
If K is not a ∗-code then there is a ∗-message over K that has two different
factorizations over K. Let this message be of minimal length. Then the two
factorizations start with different word schemata w and w 0 . Without loss
of generality, we may assume that w is a proper prefix of w 0 . This implies
w 6= # 6= w 0 and w 6∈ KV as no word in KV is a proper prefix of any word
in K. Thus w ∈ KU and w0 ∈ KV as no word in KU has a proper prefix in
KU . Thus
w = β(im−1 )/cβ(im−2 )/c · · · β(i0 )/cui0 · · · uim−2 uim−1 $
and, consequently,
w0 = β(im−1 )/cβ(im−2 )/c · · · β(i0 )/cvi0 · · · vim−2 vim−1 $#,
that is, the problem (U, V ) has (m, I) with I = (i0 , . . . , im−1 ) as a solution.
Conversely, if (U, V ) has a solution then, with w and w 0 as above, one has
w# = w0 , that is, K is not a code.
Thus, K is a ∗-code if and only if (U, V ) has no solution. As Post’s
Correspondence Problem is undecidable in general, also the property of being
a ∗-code is undecidable for linear languages. ¤
20 H. Jürgensen and S. Konstantinidis

Some of the results discussed in the present section have been extended
to infinitary or even bi-infinitary codes, that is, subsets of X ≤ω or of X ¨ . To
achieve this, the concatenation of words u, v ∈ X ¨ , so far defined only when
u ∈ X ≤−ω and v ∈ X ≤ω , is extended by letting
½
u, if u ∈ X ω ∪ X ζ ,
uv =
v, if u ∈ X ≤−ω and v ∈ X −ω ∪ X ζ .

Two notions of unique decodability need to be distinguished: the first one is

the natural extension of the notion used throughout this handbook chapter;
the second one requires unique factorizations – up to equivalence – with finite
index sets. In either case, very interesting analogues of classical results in
coding theory are obtained [136], [137], [138], [139], [72], [140].

4. Error correction, synchronization, decoding

Unique η-decodability is a necessary property to guarantee that one can read
the transmitted message. It is, however, not sufficient:
First, in the presence of noise the channel output may differ from its
input; it may not even be a message any more. In this case, the code to be
used has to satisfy additional requirements to guarantee correction or at least
detection of errors.
For example, consider the uniform code K of Example 3.1(2) and a chan-
nel γ in which at most one symbol is erased in every four consecutive symbols.
Thus the message 010101 could lead to the channel output 1010 through dele-
tion of the symbols marked by × in ×1010
0 ×.
1 The same channel output could
have been obtained from the message 010110 through ×101 0 ×0
1 or from the
message 1010 without errors.
Thus, in the presence of noise, unique decodability is quite insufficient. As
this example shows, the errors may even be such that the received erroneous
message looks like an error-free message.
Second, through noise in the received message, the recipient may not be
able to determine where the next received code word starts, that is, in essence
the recipient might not have access to the beginning (and end) of the received
message.
For example, consider the ∗-code K = {111000, 000111} used on a noisy
channel γ that permits up to one deletion among any three consecutive sym-
bols. Then
· · · 0110011001100110 · · ·
can be part of a γ-received message over K having the two γ-admissible
factorizations

· · · 0)(1100)(1100)(1100)(110 · · · and · · · 011)(0011)(0011)(0011)(0 · · · .

It is impossible to determine which factorization to accept from the available

information. Thus, the recipient has lost the synchronization with the sender.
 Codes 21

Third, the recipient may be unable to afford the cost of decoding as un-
bounded memory may be required. For example, consider the ∗-code K of
Example 3.1(4). For every n ∈ N0 , 01n ∈ K ∗ with the factorization
½
n (0)(11)(11) · · · (11), if n is even,
01 =
(01)(11)(11) · · · (11), if n is odd.

To determine even just the first factor, one has to wait until the end of the
complete message and, in the meantime, store this message in the decoder.
In this particular example one might argue, that the storage cost grows
only as log n; but this is still unbounded and, moreover, just a special property
of this example.
One could also argue in this example that the recipient can safely decode
everything following 01 in the word above as only 11 is found, possibly shifted
by one position. However, the interpretation of 11 may depend on whether
the received message starts with 0 or with 01. For example, 0 and 01 might
mean don’t use and use, respectively; and the sequence of occurrences 11
might encode what the recipient is supposed not to use or to use. Thus,
knowledge of the intermediate code words would be quite useless before the
first one is known.
To solve the first problem, one uses codes with prescribed error-correction
capabilities. To address the second problem, one introduces the notion of
synchronization delay and uses codes which are uniformly synchronous. To
address the third of these issues, one introduces the notion of decoding delay
and uses codes with bounded decoding delay, possibly even with delay 0, the
prefix codes.
In the formal language theory branch of coding theory, the notions of
synchronization delay and decoding delay are only considered for noiseless
channels.18 In this handbook chapter we develop these notions for the general
framework of P-channels. They specialize to the usual ones for the case of
noiseless channels. Moreover, we show that some fundamental properties of
these concepts continue to obtain even in the presence of noise.
Definition 4.1 Let γ be a P-channel and let η ∈ {∗, ω, −ω, ≤ω, ≤−ω, ζ, ≤ζ}.
(a) A language K is (γ, η)-detecting if it is an η-code and, for every η-
message w over K, hwiγ ∩ S(K η ) = {w}. In this case we also say that
K is a (γ, η)-detecting code.
(b) A language K is (γ, η)-correcting if it is an η-code and, for all η-messages
u and w over K with u 6= w, one has huiγ ∩ hwiγ = ∅. In this case we
also say that K is a (γ, η)-correcting code. Let Kγη be the class of (γ, η)-
correcting codes.

18
[41] is an exception; we briefly discuss that approach in Section 5. In that work
a different type of channel model is used.
22 H. Jürgensen and S. Konstantinidis

Intuitively, a code is (γ, η)-detecting if those received messages, different

from w, which one is likely to see as output of γ for an input message w
are not themselves messages over the code. A code is (γ, η)-correcting if
those received messages which one is likely to see as output of γ for an input
message w are different from the likely received messages for all other input
messages. In this case, in the spirit of maximum likelihood decoding (see [99]),
the decoder will decode any received message in hwiγ as w.
Example 4.1
(1) Consider the uniform code K of Example 3.1(2). Let γ be the channel
discussed above, that is, the channel which permits at most one deletion
in every four consecutive message symbols. Then w = 010101, v =
010110, and u = 1010 are ∗-messages over K such that u is contained in
all three intersections hwiγ ∩ hviγ , hwiγ ∩ huiγ , and hviγ ∩ huiγ . Thus, K
is not (γ, ∗)-correcting.
(2) For the same channel γ, consider the language

K = {05 101, 07 10011, 08 1101, 010 110011}.

One verifies that huiγ ∩ hviγ = ∅ for any u, v ∈ K unless u = v. Never-

theless, K is not even (γ, ∗)-correcting because

0 6 ×0011)(0
(×0 1 5
101) = (08 110×)(0
1 4 ×101)
0
∈ h(07 10011)(05 101)iγ ∩ h(08 1101)(05 101)iγ .

(3) Consider K = {0001, 01011} and a channel γ in which at most one in

every five consecutive symbols can be deleted. Then

h0001iγ = {0001, 001, 000}

and
h01011iγ = {01011, 1011, 0011, 0111, 0101}.
The set K is an ω-code. Consider an ω-message w over K. Then v ∈ hwiγ
can start with any of the word schemata in h0001iγ ∪ h01011iγ .
If v starts with 001 then w could start with 0001 or with 01011. If
the next symbol in v is 0 then w starts with 0001; if it is 1 then the
initial part of w could be ×001
0 ×1011
0 or 0×0110
1 · · · with deletions as
indicated. The first case is impossible as the two deletions are too close
to each other. Therefore, w starts with 01011. Using the fact that γ is a
P-channel, we can now remove 01011 from w and 0011 from v and look
at the remaining word schemata.
If v starts with 0001 or 000 then w starts with 0001; if it starts with
01011, 1011, 0111, or 0101 then w starts with 01011. As before, we can
remove this part from v and the corresponding code word from w.
 Codes 23

Extending these considerations one can show that K is even (γ, ζ)-
correcting.
(4) The language K = {0011, 010111} is (γ, ∗)-correcting for the channel γ
permitting at most one deletion among any six consecutive symbols. On
the other hand, because of

(0011)(10111)ω = (00111)(01111)ω
∈ h(0011)(010111)ω iγ ∩ h(010111)ω iγ

it is not (γ, ω)-correcting. Note that K is an ω-code.

Proposition 4.1 Let γ be a P-channel and K ⊆ X + . If |K| > 1 and

K ∈ Kγω ∪ Kγ−ω then K ∈ Kγ∗ . If |K| > 2 and K ∈ Kγζ then K ∈ Kγω ∩ Kγ−ω .
Proof: First, consider K ∈ Kγω with |K| > 1. By Proposition 3.1, K is a
∗-code. Let u, v be ∗-messages over K and let z ∈ huiγ ∩ hviγ . We show that
u = v. Let υ and ϕ be the factorizations of u and v, respectively, over K.
If Iυ = Iϕ = 0 then u = v = λ. Therefore, and without loss of generality,
we assume that Iϕ ≥ Iυ and Iϕ > 0. Let n = max Iϕ . As |K| > 1, there
is a w ∈ S(K) such that w 6= ϕ(n). Then uw ω , vwω ∈ S(π2 (γ)) as γ is
a P-channel. This implies zw ω ∈ huwω iγ ∩ hvwω iγ by property P2 , hence
uwω = vwω and this word schema has exactly one factorization, χ say, over
K as K is an ω-code. Moreover, χ(i) = υ(i) for i ∈ Iυ and χ(i) = ϕ(i)
for i ∈ Iϕ . If Iϕ > Iυ then ϕ(n) = w, contradicting the choice of w. Thus
Iϕ = Iυ , hence u = v. This proves the first statement for K ∈ K ω . The case
of K ∈ K−ω is proved using duality.
Now suppose that |K| > 2 and K ∈ Kζ . We show that K ∈ Kω . By
duality it then follows that K ∈ K−ω . Consider u, v ∈ S(K ω ) and z ∈
huiγ ∩ hviγ . By P0 , z ∈ S(X ω ). Let υ and ϕ be the factorizations of u
and v, respectively, over K. As |K| > 2, there is w ∈ S(K) such that w ∈ /
{ϕ(0), υ(0)}. Then w −ω z ∈ hw−ω uiγ ∩ hw−ω viγ , hence w −ω u = w−ω v. As K
is a ζ-code, this word schema has a unique factorization, up to equivalence,
over K. Let χ be such a factorization. As before, we can choose χ in such a
way that χ extends υ and ϕ. This implies υ = ϕ, hence u = v. ¤

The condition on |K| in Proposition 4.1 is needed. For example, for the
channel γ permitting at most one deletion in every six consecutive symbols,
the language {000000} is (γ, ζ)-correcting and also (γ, ω)-correcting, but not
(γ, ∗)-correcting.
In the presence of noise, the decidability problem answered for the noise-
less channel in Theorem 3.2 takes the following form: For given K, η, and γ
decide whether K is a (γ, η)-correcting code. For finite K, η = ∗ and a large
natural class of channels, one can show that this question is decidable [70].
This result, to be explained in the sequel, extends the Sardinas-Patterson
Theorem (Theorem 3.2 for finite languages and η = ∗) to noisy channels.
24 H. Jürgensen and S. Konstantinidis

The channels to be considered permit symbol substitutions, symbol in-

sertions, and symbol deletions. We give only an informal description of such
channels; a formal syntax and semantics is defined in [59]. For given integers
m ∈ N0 and L ∈ N with m < L, the channel will make at most m errors
of a given kind in any L consecutive message symbols. The errors could
be substituting a symbol for another one, inserting symbols between message
symbols, or deleting symbols in the message. The bound of m can be on the
total number of errors of all these kinds or on the number of errors for each
kind separately. Thus, this model would include a channel permitting up to a
total of five insertions and deletions in every twenty consecutive message sym-
bols and, independently, a total of up to four symbol substitutions in every
sixteen consecutive message symbols. Any channel of this kind is called an
SID-channel. The channel considered in Example 4.1(1) is an SID-channel.
The classsical theory of error-correcting codes considers almost exclusively
substitution errors. With such an error model, if the starting point of the
message is known, synchronization between coding and decoding is not an
issue of theoretical interest. For such channels, uniform codes are quite suit-
able as the uniform code word length affords the synchronization cheaply.
For certain classical error models also convolution codes have been used suc-
cessfully; the encoding for these codes is, in essence, computed by a finite
automaton, a gsm; one of their main purposes is to take message patterns
into account for encoding.
When the starting point of the message cannot be assumed to be known,
then synchronization is a difficult problem even for the substitution-only error
model and even when only block codes are considered (see, for example, [83]
and [85]).
For fast modern information transmission systems – like satellite com-
munication, communication via optical fibres, or optical data storage – the
substitution-only error model is not adequate. Errors which look like in-
sertions or deletions of symbols – regardless of their true physical nature –
are much more common; and bursts of errors, that is, errors affecting many
consecutive positions are quite likely. In this situation, the synchronization
provided for free by uniform codes may no longer help – as shown in Exam-
ple 4.1(1).
SID-channels correspond more closely to the physical error situations in
modern communication systems than the classical error models which usu-
ally only involve symbol substitutions.19 Uniform codes for the correction of
insertions and deletions have been investigated by Levenshtein in [80], [79],
[81], Sellers in [122], by Varshamov and Tenengol’ts in [141], and by Tenen-
gol’ts in [129]. Recent work on codes for physical SID channels includes [5],
[45], and [112], for instance. SID channels can be used to model certain as-
pects of speech recognition; see [2] and [3] for a probabilistic and information

19
SID channels as defined in [59] do not handle bursts well. A modification of the
model is discussed in [58].
 Codes 25

theoretic analysis of such channels. Some further related work is discussed

in Section 5 of this handbook chapter.
Theorem 4.1 [59] Every SID-channel is a P-channel.

Theorem 4.2 [70] For any finite K ⊆ X + and any SID-channel γ, it is

decidable whether K is a (γ, ∗)-correcting code.
The proof of this extension of Theorem 3.2 for finite K and η = ∗ to
noisy channels relies on a generalization of the notion of overlap: In addition
to overlaps resulting from overlapping codewords, one also needs to consider
overlaps in the received messages resulting from channel noise. Details are
provided in [70].
We now turn to the notions of synchronization, synchronization delay,
decodability, and decoding delay. They are intended to capture the following
intuition: Suppose, K is an η-code to be used with a P-channel γ and that
w0 is a γ-received η-message over K. After having received a finite or, rather,
a bounded part of w 0 one wants to be able to start the decoding and error
correction process. This process will work on w 0 in the left-to-right or right-to-
left directions or the combination of both; the latter is necessary, for instance,
when η = ζ. The process may have a definite starting point – the left end
of w0 if η ≤ ω or the right end of w 0 if η ≤ −ω. There is no such obvious
starting point for η = ζ. This latter case models, for example, the situation
when parts at the beginning and end of a received finite message have been
corrupted beyond repair and the intermediate part is not in hS(K ∗ )iγ as
symbols at the beginning and end may be missing. In this case, as a first
step, one will attempt to find a position in w 0 corresponding to a point in
the original message, where two code words were concatenated; this task is
known as synchronization. After that, one can decompose w 0 at this position
and decode the parts separately.
In the case of noiseless channels, a clear distinction can be made between
synchronization and decoding; for noisy channels involving synchronization
errors, this distinction is less clear.
Definition 4.2 Let γ be a P-channel and let η ∈ {∗, ω, −ω, ≤ω, ≤−ω, ζ, ≤ζ}.
A (γ, η)-correcting code K ⊆ X + is said to be uniformly (γ, η)-synchronous
if there is an integer n ∈ N0 such that, for all w ∈ S(K n ), all w0 ∈ hwiγ , and
all u, v ∈ S(X ≤η ) the following property obtains: If uw 0 v ∈ hS(K η )iγ then
there exist z1 , z2 ∈ S(X ≤η ) such that z1 w, wz2 ∈ S(K ≤η ), z1 wz2 ∈ S(K η )
and (u)(w 0 )(v) is γ-admissible for (z1 )(w)(z2 ).
The smallest n for which the implication in Definition 4.2 holds true is the
(γ, η)-synchronization delay of K. If n is the (γ, η)-synchronization delay of
K, it is not true in general that the implication in Definition 4.2 holds true for
any n0 with n0 ≥ n, unless γ satisfies some additional appropriate conditions20

20
For a noiseless channel the implication holds true trivially; see [4], for example.
26 H. Jürgensen and S. Konstantinidis

beyond those for a P-channel. With u, w, w 0 , v as in Definition 4.2, if uw 0 v

is a γ-received η-message over K then (u)(w 0 v) and (uw 0 )(v) are candidates
for decompositions of uw 0 v. For a noiseless channel and η = ∗, the definition
coincides with the usual one of a uniformly synchronous code (see [4]); in
this case, z1 = u, z2 = v, w = w 0 . Let Lunif-synch be the class of uniformly
(γ, ∗)-synchronous codes when γ is a noiseless channel.
Definition 4.3 Let γ be a P-channel, let η ∈ {∗, ω, −ω, ≤ω, ≤−ω, ζ, ≤ζ},
and let K ⊆ X + . A pair (x, y) of word schemata x, y ∈ hS(K ∗ )iγ is (γ, η)-
synchronizing if it has the following two properties:
(1) There are word schemata w1 , w2 ∈ S(K ∗ ) such that (x)(y) is γ-admiss-
ible for (w1 )(w2 ).
(2) For all such w1 , w2 ∈ S(K ∗ ) and for all u, v ∈ S(X ≤η ) with uxyv ∈
hS(K η )iγ , there exist word schemata z1 , z2 ∈ S(X ≤η ) such that

z1 w1 , w2 z2 ∈ S(K ≤η ), z1 w1 w2 z2 ∈ S(K η ),

and (u)(xy)(v) is γ-admissible for (z1 )(w1 w2 )(z2 ).

For a noiseless channel and η = ∗, Definition 4.3 is equivalent to the
usual definition [4]. With u, x, y, v as above and K an η-code, the γ-received
η-message uxyv can be decomposed into ux and yv and then these parts can
be decoded separately.
The assumption in Definition 4.3(1) expresses a subtle, but common prob-
lem arising in the modelling of noisy channels: If w1 and w2 are ∗-messages
over K and if x ∈ hw1 iγ and y ∈ hw2 iγ , it does not follow in general that
xy ∈ hw1 w2 iγ . For example, if γ is the channel permitting up to one deletion
in every two consecutive symbols and K = {101, 01} is the ζ-code of Exam-
ple 3.1(3), then 10 ∈ h101iγ and 1 ∈ h01iγ , but 101 ∈ / h10101iγ ; to obtain 101
from 10101, two deletions in two consecutive positions are required, contrary
to the definition of γ. Rather than being exotic, this property is inevitable
due to the statistical properties of typical physical channels with independent
source of noise. In Section 5, we summarize results which are obtained using
a channel model which always permits the concatenation of channel outputs
and we indicate how that model can be expressed in our terminology and
where the fundamental differences regarding the physical assumptions are to
be found.
The following proposition connects the notions of uniformly (γ, η)-syn-
chronous and (γ, η)-synchronizing pair. Its special case for noiseless channels
and η = ∗ is given in [4], Proposition 2.4. The proof below is based on the
ideas used in [4], but requires some additional careful analysis of admissibility
properties.
Theorem 4.3 Let γ be a P-channel, let η ∈ {∗, ≤ω, ≤−ω, ≤ζ}, and let K ⊆
X + be a (γ, η)-correcting code. The following two statements are equivalent:
(a) K is uniformly (γ, η)-synchronous.
 Codes 27

(b) There exists an integer n ∈ N0 such that every pair (x, y) with x, y ∈
hS(K n )iγ is (γ, η)-synchronizing provided there exist w1 , w2 ∈ S(K n )
with (x)(y) γ-admissible for (w1 )(w2 ).
Proof: Because of the choice of η one has Lη = L≤η for any subset L of X ∗ .
We can, therefore, use η instead of ≤η in this proof.
Assume that statement (a) is true. Let n be the (γ, η)-synchronization
delay of K. Let x, y ∈ hS(K n )iγ be such that, for some w1 , w2 ∈ S(K n ),
(x)(y) is γ-admissible for (w1 )(w2 ). Note that, as K is (γ, η)-correcting, w1
and w2 are uniquely determined if they exist. Let u, v ∈ S(X η ) such that
uxyv ∈ hS(K η )iγ .
The assumption that K is uniformly (γ, η)-synchronous implies:
(1) There exist z1 , z2 ∈ S(X η ) such that z1 w1 , w1 z2 , z1 w1 z2 ∈ S(K η ), and
(u)(x)(yv) is γ-admissible for (z1 )(w1 )(z2 ).
(2) There exist s1 , s2 ∈ S(X η ) such that s1 w2 , w2 s2 , s1 w2 s2 ∈ S(K η ), and
(ux)(y)(v) is γ-admissible for (s1 )(w2 )(s2 ).
It follows that z1 w1 , w2 s2 ∈ S(K η ) and, therefore, z1 w1 w2 s2 ∈ S(K η ). We
need to prove that (u)(xy)(v) is γ-admissible for (z1 )(w1 w2 )(s2 ).
By (1), u ∈ hz1 iγ ; by assumption, xy ∈ hw1 w2 iγ ; by (2), v ∈ hs2 iγ .
By (2), uxy ∈ hs1 w2 iγ with s1 w2 ∈ S(K η ). As x ∈ hw1 iγ and w1 ∈
S(K n ), there exist t1 , t2 ∈ S(X η ) such that t1 w1 , w1 t2 , t1 w1 t2 ∈ S(K η ) and
(u)(x)(y) is γ-admissible for (t1 )(w1 )(t2 ). Thus, uxy ∈ ht1 w1 t2 iγ , ux ∈
ht1 w1 iγ , and xy ∈ hw1 t2 iγ . Moreover, ux ∈ hz1 w1 iγ and xy ∈ hw1 w2 iγ . As
K is (γ, η)-correcting, one has t1 w1 t2 = s1 w2 , t1 w1 = z1 w1 , and w1 t2 =
w1 w2 , hence, t1 = z1 , t2 = w2 , and z1 w1 = s1 . Similarly, using xyv ∈
hw1 z2 iγ and y ∈ hw2 iγ , one shows that w2 s2 = z2 . Hence, z1 w1 w2 = s1 w2 ,
w1 w2 s2 = w1 z2 , and z1 w1 w2 s2 = s1 w2 s2 . Therefore, uxy ∈ hz1 w1 w2 iγ ,
xyv ∈ hw1 w2 s2 iγ , and uxyv ∈ hz1 w1 w2 s2 iγ as needed.
For the converse, assume that statement (b) is true. Let w ∈ S(K n+n ),
w ∈ hwiγ , and u, v ∈ S(X η ) with uw 0 v ∈ hS(K η )iγ . There are w1 , w2 ∈
0

S(K n ) with w1 w2 = w. By property P1 , there are x, y ∈ S(X η ) such that

w0 = xy and (x)(y) is γ-admissible for (w1 )(w2 ). By assumption (x, y) is
a (γ, η)-synchronizing pair. Hence, there exist z1 , z2 ∈ S(X η ) such that
z1 w1 , w2 z2 , z1 w1 w2 z2 ∈ S(K η ), and (u)(xy)(v) is γ-admissible for the factor-
ization (z1 )(w1 w2 )(z2 ). Thus, K is uniformly (γ, η)-synchronous. ¤

Example 4.2 Consider the code K = {0001, 01011} over the alphabet X =
{0, 1}. For the noiseless channel γ, K is uniformly (γ, ∗)-synchronous with
delay 1. On the other hand, if γ is the channel permitting at most one deletion
in every five consecutive symbols then K is not uniformly (γ, ∗)-synchronous.
First note, that K is (γ, ∗)-correcting. A γ-received ∗-message over K
will start with 000, 0010, 0011, 010, 011, or 101; in the first two cases, the
first code word used is 0001 and in the latter four it is 01011 – due to the
characteristics of γ. Moreover, the start of the factorization of the received
28 H. Jürgensen and S. Konstantinidis

message is unique as no code word is subject to more than one error.21 By

induction this proves that K is indeed (γ, ∗)-correcting.
Now suppose that K is uniformly (γ, ∗)-synchronous with delay n and
let x = (1011)n ∈ h(01011)n iγ . Consider u = 001 and v = 1. Then
uxv = 001(1011)n 1 = (0011)(0111)n ∈ h(01011)n+1 iγ , but xv = (1011)n 1 ∈
/
hS(K ∗ )iγ .

Definition 4.4 Let η ∈ {∗, ≤ω}. A (γ, η)-correcting code K ⊆ X + is said

to be right (γ, η)-decodable if there is a constant d ∈ N with the following
property: For all w ∈ S(K η ), all w0 , x, y ∈ S(X η ), all u, u0 ∈ S(K), and all
v ∈ S(K d ), if xw0 ∈ hu0 wiγ , xy ∈ Pref(xw 0 ), and if (x)(y) is γ-admissible
for (u)(v), then u = u0 and w0 ∈ hwiγ .
The smallest d such that K is right (γ, η)-decodable22 with delay d is
called the right (γ, η)-decoding delay of K. Let d be the right (γ, η)-decoding
delay of K. As in the case of the synchronization delay, it is not true in
general, that K is also right (γ, η)-decodable with delay d0 for any d0 ≥ d.
This can be guaranteed only when γ satisfies certain additional conditions
beyong being a P-channel. It is trivially true for the noiseless channel. Let
Lrdecodable and Lldecodable be the classes of right (γ, ∗)-decodable codes and
left (γ, ∗)-decodable codes, respectively, when γ is a noiseless channel. 23
Remark 4.1 With K, η, γ, x, u, w, and w 0 as in Definition 4.4, if K is right
(γ, η)-decodable then (x)(w 0 ) is γ-admissible for (u)(w).
Assume that K is right (γ, η)-decodable with delay d. By Remark 4.1,
once the decoder has seen an initial part of the received message that could
have been the output resulting from an input of d + 1 consecutive code words
and if, within this initial part, a factorization into the output for the first
code word followed by the output for the next d code words is possible, then
output x corresponding to the first code word – and, hence, that code word u
– is uniquely identified. Moreover, the remainder w 0 of the received message
is possible as an output for w and the concatenation uw as input could have
yielded xw 0 , given the properties of γ. Thus, Definition 4.4 correctly captures
the idea of left-to-right decoding with a bounded delay.

21
Note: This argument is only true for this particular type of situation; it cannot
be generalized.
22
Instead of decodable and decoding delay often also the terms decipherable and
deciphering delay are used; see [4], for example.
23
The codes in Lrdecodable are usually referred to as codes with finite decoding (or
deciphering) delay; see [4]. In [128] they are called codes with bounded decoding
delay; the codes with finite decoding delay of that work form a different and larger
class of codes. In [44] and [14] algorithms are presented for determining the decoding
and synchronization delays of finite ∗-codes, and the complexity of these algorithms
is determined.
 Codes 29

Example 4.3 Let X = {0, 1} and let γ be the channel permitting at most one
deletion in every four consecutive symbols. Let K = {u, v} with u = 0011
and v = 1100. K is (γ, ω)-correcting. Consider the input word

(uv)ω = 0011110000111100 · · ·

over K with the unique factorization

(0011)(1100)(0011)(1100) · · · .

The word w 0 = 00111000111000111000 · · · is possible as an output of γ

for w as input. Note that w 0 has two γ-admissible factorizations, that is,
w0 = (001)(110)(001)(110) · · · and w 0 = (0011)(100)(011)(100)(011)(100) · · ·.
This illustrates the point that, even if K is (γ, ω)-correcting, a γ-received
ω-message need not have a unique factorization over hS(K)iγ . Nevertheless,
the decoding is unique and K is right (γ, ω)-decodable with delay 0.
As in the case of synchronization, the notion of decodability and of de-
coding delay is equivalent to the usual one when η = ∗ and γ is noiseless (see
[4], II.8, ans [128]). A more restrictive notion, counting the delay in terms of
symbols rather than code words, is used in [57]. That definition implies the
conditions of Definition 4.4 when K is finite, albeit with different values for
the delays. By duality, one defines the notions of left (γ, η)-decodability and
left (γ, η)-decoding delay for η ∈ {∗, ≤−ω}.
As in the case of noiseless channels, also for P-channels the synchroniza-
tion delay is an upper bound of the right decoding delay.
Theorem 4.4 Let η ∈ {∗, ≤ω}, let γ be a P-channel and let K ⊆ X + be
(γ, η)-correcting. If K is uniformly (γ, η)-synchronous with delay n then K
is right (γ, η)-decodable with delay n.
Proof: Consider x, y, w 0 ∈ S(X η ), w ∈ S(K η ), u, u0 ∈ S(K), and v ∈ S(K n )
such that xw 0 ∈ hu0 wiγ , xy ∈ Pref(xw 0 ), and (x)(y) is γ-admissible for
(u)(v). Hence, x ∈ huiγ , y ∈ hviγ , xy ∈ huviγ , and there is t ∈ S(X η ) with
xw0 = xyt.
As K is uniformly (γ, η)-synchronous with delay n, there are z1 , z2 ∈
S(X η ) such that z1 v, vz2 , z1 vz2 ∈ S(K η ) and (x)(y)(t) is γ-admissible for
(z1 )(v)(z2 ). As K is (γ, η)-correcting, one has u0 w = z1 vz2 and uv = z1 v,
hence u = z1 and u0 w = u(vz2 ). This implies u = u0 , w = vz2 , and yt = w 0 ∈
hwiγ . ¤

For noiseless channels γ, the finite right (γ, ∗)-decodable codes are pre-
cisely the finite ω-codes.
Theorem 4.5 [74], [78] For a finite set K ⊆ X + , one has K ∈ Lrdecodable if
and only if K ∈ Kω .
30 H. Jürgensen and S. Konstantinidis

Theorem 4.6 Lunif-synch ( Kζ .

Proof: Let K ∈ Lunif-synch with delay d. Then, K ∈ Lrdecodable ∩Lldecodable [4]
and K ∈ K−ω ∩ Kω [128]. Consider w ∈ S(X ζ ) and two factorizations ϕ and
ψ of w over S(K) with Iϕ = Iψ = ζ. We show that ϕ ∼ ψ.
Assume there are indices k, l ∈ ζ such that ϕ(k) and ψ(l) start at the
same index in w. Then
· · · ϕ(k − 2)ϕ(k − 1) = · · · ψ(l − 2)ψ(l − 1)
and
ϕ(k)ϕ(k + 1) · · · = ψ(l)ψ(l + 1) · · · .
This implies ϕ ∼ ψ as K ∈ K−ω ∩ Kω .
Now assume that there are no such indices k and l. Then there are
indices n, m, i ∈ ζ and a proper prefix p of ϕ(n) such that p is a proper
suffix of ψ(m), the last symbol of p and ψ(m) are at position i in w, that is,
w(i − |p| + 1) · · · w(i) is an instance of p as a prefix of an instance of ϕ(n) and
an instance of ψ(m) ends at w(i). The situation is shown more completely
in Fig. 4.1. Let s be such that ϕ(n) = ps. Then s 6= λ and s is proper prefix
of ψ(m + 1) or ψ(m + 1) is a proper prefix of s.
Let t, r ∈ N with t ≥ d be such that one has the situation shown in Fig. 4.1.
Such t and r exist. Let p0 be the proper prefix of ϕ(n + t + 1) which overlaps
or contains ψ(m + r) and let s0 be such that ϕ(n + t + 1) = p0 s0 . Thus,
ψ(m + 1) · · · ψ(m + r) = sϕ(n + 1) · · · ϕ(n + t)p0 .
Because of t ≥ d one has
sϕ(n + 1) · · · ϕ(n + t) ∈ S(K ∗ )
and
ϕ(n + 1) · · · ϕ(n + t)p0 ∈ S(K ∗ ).
As p0 6= λ, there is an h ∈ N such that
ϕ(n + 1) · · · ϕ(n + t)p0 = u0 · · · uh−1
for some u0 , . . . , uh−1 ∈ S(K). Thus
ϕ(n + 1) · · · ϕ(n + t)ϕ(n + t + 1) · · · = u0 · · · uh−1 ψ(m + r + 1) · · ·
and, as K ∈ Kω , ui = ϕ(n+i+1) for all i ∈ h, hence ϕ(i) = ψ(i−n−h+m+r)
for all i with n + h + 1 ≤ i. On the other hand,
· · · ϕ(n) · · · ϕ(n + h) = · · · ψ(m) · · · ψ(m + r)
−ω
and K ∈ K imply that ϕ(i) = ψ(i − n − h + m + r) for all i with i ≤ n + h.
Thus ϕ ∼ ψ and K ∈ Kζ .
Finally, consider
K = {010, 20} ∪ 2(001)∗ .
One has K ∈ / Lunif-synch ; however, K ∈ Kζ ,
/ Lrdecodable by [128], hence K ∈
ζ
hence Lunif-synch ( K . ¤
 Codes 31

p s p0 s0
.................................................................... ....................................................................

··· ϕ(n) ϕ(n + 1) ··· ϕ(n + t) ϕ(n + t + 1) ···

....................................................................................................................................................................................................................................................................................................................................................................................................................
··· ψ(m) ψ(m + 1) ··· ψ(m + r) ψ(m + r + 1) · · ·

Fig. 4.1. The factorization situation in the proof of Theorem 4.6.

5. Homophonic codes
In cryptography, a homophonic cipher is a system which, to every source
symbol, may assign several encryptions (see [67], for example). The purpose
of a homophonic cipher is to obscure statistical properties of the message. For
example, for a message in plain English, a homophonic cipher would provide
many different encodings of the most frequent letters – like the letter e – so
that applying a statistical analysis to the cryptogram would not expose its
encryption. Cryptographic aspects of homophonic ciphers are discussed in
[37] and [53]; see also [60] for an analysis of the limitations of the method.
A homophonic encoding f of an alphabet X into an alphabet Y is a
mapping of X into the set of non-empty subsets of Y + , the idea being that,
for encoding a word over X, one independently and non-deterministically
encodes each symbol in the word according to f and then concatenates the
results. Such encodings have been investigated in [117], [12], [15], and [13] as
multi-valued codes. Beyond their cryptographic interpretation, homophonic
codes can also be considered in the context of error correction. To do so, we
construct a channel from a given homophonic code in such a way that the
error behaviour of the channel reflects the variations of possible encodings.
Our construction is slightly more general than required for homophonic codes.
The foundations of the theory of channels and codes – of error correction,
synchronization, and decoding – in the framework to which the homophonic
codes belong was first given in a series of articles leading to and later com-
bined in the book [41] of 1974. To our knowledge, this was the first system-
atic attempt to lay the foundations of a comprehensive and uniform theory
of variable-length codes for noisy channels. We explain below how that work
relates to the model used in this handbook chapter. For detailed results of
that research we refer the book [41] itself.
Definition 5.1 Let X and Y be alphabets and f ⊆ X × Y ∗ . Let
¡ ¢
K = f (X) = {w | ∃x ∈ X (x, w) ∈ f }.
A word schema y ∈ S(Y ¨ ) is an f -encoding of a word schema x ∈ S(X ¨ ) if
there is a factorization ϕ of y over K such that Iϕ = Ix and (x(i), ϕ(i)) ∈ f
for all i ∈ Ix .
Let Ff ⊆ X ¨ × Y ¨ be the relation
Ff = {(x, y) | x ∈ X ¨ , y ∈ Y ¨ , S(y) is an f -encoding of S(x)}.
The relation Ff is the encoding determined by f .
32 H. Jürgensen and S. Konstantinidis

In the special case, when f is a mapping and x and y are ∗-words, y is

an f -encoding24 of x if and only if y is the image of x under the morphism
of X ∗ into Y ∗ induced by f . Definition 5.1 extends this notion to the cases
when f is a many-to-many relation25 and when x and y are infinite. We now
exhibit a general construction of channels representing relations in X × Y +
including homophonic codes.
Definition 5.2 Let X and Y be alphabets, let K be a ∗-language over Y with
|K| = |X|, and let g be a bijection of X onto K. Let f ⊆ X × Y + . The
channel γg,f defined as

¯ y, y 0 ∈ S(Y ¨ ), n, n0 ∈ Z,
½ ¯ ¾
0 0
γg,f = ([[y , n ]] | [[y, n]]) ¯
¯
∃x ∈ X ¨ (x, y) ∈ Fg ∧ (x, y 0 ) ∈ Ff
¡ ¢

is called the channel generated by g and f .

Definition 5.2 exhibits some arbitrariness as to how physical errors are
modelled by a relation f – a homophonic code in our special case – due to
the required encoding g.
Example 5.1 Let X = {0, 1} = Y and

f = {(0, 111), (0, 110), (0, 101), (0, 011), (1, 000), (1, 001), (1, 010), (1, 100)}.

If g maps 0 onto 111 and 1 onto 000 then the resulting channel permits at
most one substitution in every code word. Thus, for example, (110 | 111)
would be a possible channel behaviour. On the other hand, if g maps 0 onto
000 and 1 onto 111 then the channel would be quite different; for example
(111 | 000) would be a possible channel behaviour.
Not every channel of the form γg,f is an SID channel. This is true even
under severe restrictions on g and f . As shown in Example 5.1, the possible
errors are determined by a given factorization of the input message whereas,
for an SID channel, the possible error patterns – like one insertion in every
five consecutive symbols – do not and cannot take a given factorization into
account.26 Conversely, not all SID channels can be modelled in the form γf,g .
In a strict sense, the SID channel model may be closer to the physical error
situation; practically, the differences may be not so important.
In general, channels of the form γg,f may not even be P-channels. How-
ever, under some natural assumptions they have most of the essential prop-
erties of P-channels.

24
The notion of encoding is not intended to imply unique decodability.
25
A homophonic code can be considered as a one-to-many relation.
26
The same problem arises, by the way, also with the classical substitution-error
model for block codes as, for instance, expressed by the Hamming or Lee metrics;
also there, a factorization is assumed to be given.
 Codes 33

Proposition 5.1 Let X and Y be alphabets, let K be a ζ-code (in the usual
sense) over Y with |K| = |X|, and let g be a bijection of X onto K. Let
f ⊆ X × Y + such that, g ⊆ f . The channel γg,f is stationary and satisfies
conditions P0 , P1 , P2 , and P3 .
Proof: If ([[w 0 , n0 ]] | [[w, n]]) ∈ γg,f then ([[w 0 , k 0 ]] | [[w, k]]) ∈ γg,f for every
k, k 0 ∈ Z and, therefore, γg,f is stationary.
Condition P0 is satisfied as, for all x ∈ X, g(x) ∈ Y + and π2 (f ) is a
non-empty subset of Y + .
Condition P2 is satisfied as g ⊆ f and γg,f is stationary.
Condition P3 is satisfied as (λ, λ) ∈ Ff ∩ Fg .
We turn to proving that condition P1 is satisfied. Consider (y 0 | y) ∈ γg,f .
Let y = [[w, n]] and y 0 = [[w0 , n0 ]] where w, w 0 ∈ S(Y ϑ ) for some ϑ ≤ ζ. Let ϕ
be a factorization of w over some set Z ⊆ S(π2 (γg,f )) ∩ S(X + ) with Iϕ 6= ∅.
Note that S(π2 (γg,f )) = S(π2 (Fg )). Thus [ϕ] ∼ w and w 6= λ 6= [ϕ]. As
w ∈ S(π2 (Fg )), there exists x ∈ S(X ϑ ) and a factorization κ of w over K
such that Ix = Iκ and g(x(i)) = κ(i) for all i ∈ Ix . As [κ] ∼ w, Iκ 6= ∅.
As K is a ζ-code, there are, for all i ∈ Iϕ , unique ri ∈ Iκ = Ix and li ∈ N0
such that ϕ(i) = κ(ri ) · · · κ(ri + li ) and ri+1 = ri + li + 1.
Similarly, there is a factorization κ0 of w0 over S(π2 (f )) such that Iκ0 =
Ix = Iκ and, for all i ∈ Ix , (x(i), κ0 (i)) ∈ f .
We define a factorization ϕ0 as follows: Let Iϕ0 = Iϕ and, for i ∈ Iϕ , let
ϕ (i) = κ0 (ri ) · · · κ0 (ri + li ). Then [ϕ0 ] ∼ [κ0 ] ∼ w0 .
0

Consider an index mapping ψ : I → Iϕ with I 6= ∅. We need to show that,

for all n, n0 ∈ Z, ([[[ϕ0 ψ], n0 ]] | [[[ϕψ], n]]) ∈ γg,f . For this, it suffices to show
that there is a word z ∈ X ≤ζ such that (z, [ϕψ]) ∈ Fg and (z, [ϕ0 ψ]) ∈ Ff .
Let χ : Iϕ → X + be given by χ(i) = x(ri ) · · · x(ri + li ) for i ∈ Iϕ . Then
z = [χψ] has the required properties. ¤

Proposition 5.1 helps to understand and clarify the importance of con-

dition P1 . The condition establishes that any factorization of the input,
whichsoever, has a corresponding factorization of the output. A channel γ g,f
according to Proposition 5.1 is nearly a P-channel: The only difference is
that, usually, π2 (γg,f ) 6= I(Y ¨ ). Thus, a channel of the form γg,f models
the input-output behaviour of a P-channel under the assumption that only
messages over the chosen and fixed ζ-code K are sent. On the other hand, a
P-channel in general models the behaviour of physical channels under arbi-
trary inputs.
We now turn to the decoding of messages encoded using homophonic
codes or – in general – arbitrary relations.
Definition 5.3 Let X and Y be alphabets and let f ⊆ X × Y + such that, for
every x ∈ X, f (x) 6= ∅. For η ∈ {∗, ω, −ω, ζ, ≤ω, ≤−ω, ≤ζ}, f is said to be
uniquely η-decodable if, for every y ∈ π2 (Ff ) ∩ Y η there is one and only one
x ∈ X η such that (x, y) ∈ Ff .
34 H. Jürgensen and S. Konstantinidis

The connection between the two notions of unique η-decodability intro-

duced in this handbook chapter, that of Definition 3.4 for languages and that
of Definition 5.3 for relations, is expressed in the following statement for the
case when f is a mapping (see [4] or [123]).
Theorem 5.1 Let X and Y be alphabets and let f be a mapping of X into
Y + . Then f is uniquely η-decodable if and only if f is injective and f (X) is
an η-code.
Note that, if f is uniquely η-decodable, then f is also uniquely η 0 -decod-
able for η 0 < η. The following theorem explains a connection between decod-
ing for the encoding determined by a relation f and error correction for the
channel γg,f for some g.
Theorem 5.2 Let X and Y be alphabets and let f ⊆ X × Y + such that, for
every x ∈ X, f (x) 6= ∅. Let η ∈ {∗, ω, −ω, ζ, ≤ω, ≤−ω, ≤ζ}. The relation f
is uniquely η-decodable if and only if there is an η-code K and a bijection g
of X onto K such that K is (γg,f , η)-correcting.
Moreover, if f is uniquely η-decodable then g can be chosen to satisfy
g ⊆ f and any such choice g results in g(X) being (γg,f , η)-correcting.
Proof: First, assume that f is uniquely η-decodable, hence, also uniquely ∗-
decodable. For every x ∈ X, select a cx ∈ Y + such that (x, cx ) ∈ f . Let
K = {cx | x ∈ X} and let g : X → K be the mapping with g(x) = cx . The
fact that f is uniquely ∗-decodable implies that f (x) ∩ f (x0 ) = ∅ if x 6= x0 ,
x, x0 ∈ X. Therefore, g is bijective.
Consider w ∈ K η and a factorization ϕ of S(w) over K. Let ψ be the map-
ping of Iϕ into X defined by ψ(i) = g −1 (ϕ(i)) for i ∈ Iϕ . Thus (ψ(i), ϕ(i)) ∈ g
and, by g ⊆ f , also (ψ(i), ϕ(i)) ∈ f , hence, (v, w) ∈ Ff where v ∈ X η is the
word given by [ψ]. By assumption, v is unique.
Suppose, ϕ0 is also a factorization of S(w) over K. Let ψ 0 be the corre-
sponding mapping of Iϕ0 into X defined as above. The uniqueness of v implies
[ψ] ∼ S(v) ∼ [ψ 0 ], hence Iϕ = Iψ = Iψ0 = Iϕ0 . Moreover, if ψ(i) = ψ 0 (j) = x
for some i, j ∈ Iψ , then ϕ(i) = g(x) = ϕ0 (j). Therefore, ϕ and ϕ0 are
equivalent. This proves that K is an η-code.
Now consider η-messages u and w over K such that there is a γg,f -received
η-message z ∈ huiγg,f ∩ hwiγg,f . There are words x, y ∈ X ¨ such that
(x, u), (y, w) ∈ Fg and (x, z), (y, z) ∈ Ff . As f is uniquely η-decodable, one
has x = y and, therefore, u = w. This shows that K is (γg,f , η)-correcting.
For the proof of the converse implication, assume that there is an η-code
and a bijection g of X onto K such that K is (γg,f , η)-correcting. Consider
y ∈ S(Y η ) and x, z ∈ S(X η ) such that (x, y), (z, y) ∈ Ff . Let ϕ : Ix → K
and ψ : Iz → K be given by ϕ(i) = g(x(i)) and ψ(i) = g(z(i)), respectively.
Hence, (x, [ϕ]) and (z, [ψ]) are in Fg . Therefore, y ∈ h[ϕ]iγg,f ∩ h[ψ]iγg,f . As
K is (γg,f , η)-correcting, one has [ϕ] ∼ [ψ]. This implies x ∼ z because g is
injective. Thus, f is uniquely η-decodable. ¤
 Codes 35

In [13] also the notion of a fault-tolerant homophonic code is investigated.

This notion can be expressed in our general framework for channels. However,
a natural error-model has yet to be developed to capture the type of faults
against which these codes are tolerant. These faults include certain insertion
and deletion faults – or more generally, synchronization faults – and fault-
tolerance is shown to be equivalent with the property that the decoding can
be achieved using a finite-state transducer in which every state can serve as
the initial state. Such decoders are also considered in [77] and [111] and are
presented in some detail in the Section 11.
+
Theorem 5.3 [117] Let f : X → 2Y6=∅ be a homophonic encoding such that,
for every x ∈ X, the set f (x) is finite. It is decidable, whether f is uniquely
∗-decodable.
As before, the notions of decoding delay and synchronizability can be
introduced in a natural way for homophonic codes. In [12], a characterization
of homophonic codes having these properties is provided. The construction of
transducers achieving the decoding is shown in [15] (see also [116] and [117]).

6. Methods for defining codes

A language K ⊆ X + is a ∗-code if every ∗-message over K has a unique fac-
torization over K. Thus, ∗-codes are characterized by the following property:

 For all n, m ∈ N and all u0 , u1 , . . . , un−1 , v0 , v1 , . . . , vm−1 ∈
(Ccode ) K, if u0 u1 · · · un−1 = v0 v1 · · · vm−1 then n = m and ui = vi
 for i ∈ n.

In algebraic terms this says that a language K is a code if and only the
semigroup generated by K, with concatenation of words as multiplication, is
free with K as a free set of generators.27 Condition Ccode can be considered
as expressing a kind of independence among the elements of K.
Many different classes of codes have been introduced to satisfy various
constraints regarding decodability, synchronizability, or fault-tolerance. The
classes of infix codes and solid codes mentioned before are examples of such
classes – constructed to avoid certain overlap situations which could some-
times render decoding difficult. More about the latter of these two classes of
codes is said in Section 11.
In this section we analyse the idea underlying most constructions of nat-
ural classes of codes. The key notion is that of independence in universal
algebra. Independence in the sense of being a free set of generators is the
special example defining the class of all codes.
Dependence theory in universal algebra extends ideas from linear algebra
to other types of algebras and deals with notions of the following kind: in-
dependent set; an element depends on a set; span of a set; minimal spanning

27
This property can be simplified by assuming already that n = m [123].
36 H. Jürgensen and S. Konstantinidis

set; dimension. In essence, this theory has two branches which have very
little in common: one based on a purely set theoretic model and one based
on the notion of freeness in algebras. An introduction to the former can be
found in [16];28 for the latter, an introduction is given in [34]. The relation
between the two approaches is analysed in [31]. We follow the former, as it
is suitable for the problem.29
We now outline the basic concepts of dependence theory. We give a few
more details than absolutely required for our application to help the reader
put the concepts into a broader context.
Definition 6.1 Let S be a set. A dependence system on S is a subset D of
2S which has the following property: L ∈ D if and only if there is a finite,
non-empty subset L0 of L with L0 ∈ D. The subsets of S which are in D are
called D-dependent. All other subsets of S are D-independent.
By definition, every subset of an independent set is independent; in par-
ticular, the empty set is independent. Every superset of a dependent set is
dependent.
Example 6.1 Let S = X + for an alphabet X. Let Dcode be the set of all
non-empty subsets L of X + which are not codes, that is, which are not freely
generating L+ . Thus, a set K ⊆ X + is Dcode -independent if and only if there
is no finite subset L of K which does not freely generate L+ , that is, if and
only if K is a code.
In Definition 6.1, the set L0 can be of any size. We also need a notion of
dependence for the case when the size of L0 is bounded.
Definition 6.2 Let n ∈ Nℵ0 . A dependence system D on the set S is said to
be an n-dependence system if and only if it satisfies the following condition:
L ∈ D if and only if there is a non-empty subset L0 of L with |L0 | < n and
L0 ∈ D.
Of course, an ℵ0 -dependence system is just a dependence system without
any restriction. The dependence system of Example 6.1 is an ℵ0 -dependence
system; as a consequence of results in [51] one finds that it is not an n-
dependence for any n ∈ N. In the context of universal algebra in general,
that is, not just that of semigroups, the dependence described in Example 6.1
is sometimes called standard dependence.
For n ∈ Nℵ0 , let D(n) (S) be the class of n-dependence systems on S. We
usually omit n when n = ℵ0 . For D ∈ D(n) (S), let LD be the family of

28
The relevant chapter of that book contains several errors; see [32] for corrections
and further explanations.
29
Note that dependence theory in the sense to be used is part of the general
framework of the theory of matroids [143]. In our specific case, that of classes of
codes, however, the more restrictive properties of matroids never obtain.
 Codes 37

D-independent subsets of S. Let L(S) be the class {LD | D ∈ D(S)} and let
L(n) (S) = {LD | D ∈ D(n) (S)}.
Remark 6.1 Let D and D 0 be an n-dependence system and an n0 -dependence
system on the set S, respectively. Then D ∪ D 0 is an m-dependence system
on S with m = max(n, n0 ).
In contrast to Remark 6.1, the intersection of two dependence systems
need not be a dependence system.
Definition 6.3 Let D be a dependence system on S, and let a ∈ S and
X ⊆ S. The element a is said to depend on X if a ∈ X or if there is an
independent subset X 0 ⊆ X such that X 0 ∪ {a} is dependent. The span of X,
hXi, is the set of all elements of S which depend on X. If X is independent
and hXi = S then X is called a basis of S. A set X is said to be closed if
hXi = X.
Of course, the standard example of dependence is linear dependence in
vector spaces. We are, however, concerned with far more general depen-
dences. We review some of the basic properties of dependence systems needed
in our present context.
Recall that a mapping C : 2S → 2S is a closure operator if, for every
X ⊆ S, one has X ⊆ C(X) and C(C(X)) = C(X) and, moreover, X ⊆ Y
implies C(X) ⊆ C(Y ) for all X, Y ⊆ S. A closure system on S is a set C ⊆ 2S
which is closed under arbitrary intersections. With a closure system C one
associates the closure operator CC by
\
CC (X) = Y.
X⊆Y ∈C

Conversely, with a closure operator C one associates a closure system C C by

CC = {X | X ⊆ S, C(X) = X}.

This correspondence between closure operators and closure systems is bijec-

tive and CCC = C, CCC = C. A closure operator C is said to be algebraic if,
for every X ⊆ S and every a ∈ S, a ∈ C(X) implies that there is a finite sub-
set X 0 of X such that a ∈ C(X 0 ). A closure system C is said to be algebraic
if the corresponding closure operator CC is (see [16]).
Lemma 6.1 Let D be a dependence system on S.
(a) If a ∈ S depends on X ⊆ S then there is a finite independent subset X 0
of X such that a depends on X 0 [16].
(b) For every X ⊆ S one has X ⊆ hXi. For every X, Y ⊆ S, X ⊆ Y implies
hXi ⊆ hY i [32].
(c) The set of closed subsets of S forms an algebraic closure system [16].
38 H. Jürgensen and S. Konstantinidis

In general, the span does not satisfy the equation hXi = hhXii. For
example, let S = {a, b, c} and D = {{a, b}, {b, c}, {a, b, c}}. Then ∅, {a},
{b}, {c}, and {a, c} are the independent sets. Clearly, hai = {a, b} and
hhaii = {a, b, c}.

Definition 6.4 Let D be a dependence system on S. The dependence is said

to be transitive if hhXii = hXi for every X ⊆ S.

Transitive dependence systems have been studied under several different

names (see [143], p. 7). The collection of independent sets of a transitive
dependence on a finite set is known as a matroid [143]. For a discussion of
the problems concerning the definition of infinite matroids see Chapter 20
of [143].
Transitivity is a very natural requirement for a dependence relation as
shown in the following characterization result:

Theorem 6.1 [16] Let S be a set.

(1) If D is a transitive dependence, then the mapping X → hXi is an alge-
braic closure operator with the exchange property

y∈
/ hXi ∧ y ∈ hX ∪ {z}i ⇒ z ∈ hX ∪ {y}i.

(2) If α : 2S → 2S is an algebraic closure operator with the exchange property

y∈
/ α(X) ∧ y ∈ α(X ∪ {z}) ⇒ z ∈ α(X ∪ {y}),

then there is a transitive dependence D such that α(X) = hXi for all
X ⊆ S.

For transitive dependence systems, one can define the notions of basis
and dimension in a meaningful way. For vector spaces, for example, linear
dependence defines dependence systems; the basis and dimension obtained
in this way coincide with their linear counterparts.
In the context of the theory of codes, the set S is the free semigroup X + ,
that is, the set of all non-empty finite words over X with concatenation as
the multiplication operation. The dependence considered in Example 6.1 is
an example of a standard dependence [16], [31]. In this case, the dependence
is not transitive as shown by the following example.

Example 6.2 Let X = {0, 1} and consider the words v = 01, w = 0110,
u = 100110, and z = 010110. Then the sets {u, v}, {v, w}, and {u, v, z} are
codes, while the sets {u, v, w} and {v, w, z} are not codes. Thus, w ∈ hu, vi,
z∈/ hu, vi, but z ∈ hhu, vii.
 Codes 39

We now use the framework of dependence systems to define several classes

of codes. For each class, we provide a brief explanation of its properties.
Each class is identified by an abbreviation of its name. For example, the
dependence system Du defines the class Lu of uniform codes and we refer
to the condition defining this dependence system as Cu . The connection
between these classes of codes is presented in Section 7 where also some
additional properties of dependence systems are presented as required. The
references given for the classes of codes point to additional information about
these classes; usually these references do not employ the notion of dependence
system for their definitions and analyses.
• The classes Ln-code of n-codes for n ∈ N:
 A set L ⊆ X + is Dn-code -dependent if and only if there is


(Cn-code ) a non-empty subset L0 of L with |L0 | ≤ n such that L0 is

Dcode -dependent [48], [51].


Thus, a language K is an n-code if and only if every subset of K with at

most n elements is a code. The n-codes form a proper hierarchy
+
K∗ = Lcode ( · · · ( L(n+1)-code ( Ln-code ( · · · L2-code ( L1-code = 2X
+
with K∗ and 2X as lower and upper bounds, respectively.
If K is a code over X and w1 , . . . , wn are distinct elements of K then
the set K ∪ {w1 · · · wn } is an n-code, but not an (n + 1)-code [48]. This also
shows that, for every n, there is an n-code which is not a code.
• The 2-codes are of particular interest due to the fact that a two-element
set {u, v} is a code if and only if uv 6= vu (see [123]). Thus D2-code can also
be defined by the following condition expressing anti-commutativity for the
independent sets.
A set L ⊆ X + is Dac -dependent if and only if uv = vu for
½
(Cac )
some u, v ∈ L with u 6= v.
Thus L2-code = Lac . No similar characterization is known for any of the
classes of n-codes with n > 2. Indeed no simple characterization of the n-
element sets which are codes is known for n > 2. In [69] the 3-element sets
which are codes are characterized (see also [68]); due to its complexity, this
characterization seems to be very difficult to apply in the analysis of 3-codes.
A language K is a 2-code if and only if, for every primitive word w, there
is at most one n ∈ N such that w n ∈ K. This is a consequence of the
characterization of L2-code by Lac . In contrast, for n ≥ 3, if K is an n-code
then there are infinitely many primitive words w such that w n ∈ / K for all
n ∈ N [48].
The class of n-codes is defined by an (n + 1)-dependence system. There is
no n0 -dependence system with n0 < n+1 by which this class could also be de-
fined. This follows from general properties of dependence systems explained
in Section 7 below.
40 H. Jürgensen and S. Konstantinidis

• The class Lp of prefix codes:

A language L ⊆ X + is Dp -dependent if there are u, v ∈ L

½
(Cp )
such that u is a proper prefix of v.

Prefix codes have been studied extensively – see [4] for an account of the
work until about 1985. Every prefix code is a code. However, for example,
the set {0, 01} is a code, but not a prefix code.
Prefix codes have (right) decoding delay 0 for a noiseless channel. As a
consequence, every prefix code is an ω-code. The language {0, 10, 11} is a
prefix code, but not a (−ω)-code.
For most major results of information theory, the restriction from codes to
prefix codes does not make a difference of any significance. Prefix codes have
a natural interpretation as labelled trees – each code word describes a path
from the root to a leaf – and, hence a natural description by automata. Their
tree description applies to algorithmic problems, like searching or sorting.
Decisions in a search algorithm correspond to the choice of the next symbol
in a code word and, hence, the number of decisions in a search is bounded
from below by the length of the corresponding code word. An excellent
account of the application of prefix codes to the analysis of algorithms can
be found in [1].
• By duality, one defines the class Ls of suffix codes:

A language L ⊆ X + is Ds -dependent if there are u, v ∈ L such

½
(Cs )
that u is a proper suffix of v.

Properties of suffix codes can be derived trivially from properties of prefix

codes using duality. For example, every suffix code is a (−ω)-code.
In general, prefix codes and suffix codes need not be ζ-codes: Suppose
K is a prefix code which is not a (−ω)-code. Let u ∈ K −ω be such that u
has two non-equivalent factorizations over K and let v ∈ K ω ; then uv has at
least two non-equivalent factorizations over K, that is, K is not a ζ-code.
• The construction leading to the classes of n-codes has no meaningful
counterpart for prefix codes or suffix codes alone: If K is a language such
that every two-element subset is a prefix code then, clearly, K is a prefix
code. However, the following construction starting from both prefix codes
and suffix codes yields some objects – and a phenomenon – of mathematical
interest, the classes of n-ps-codes for n ∈ N, n ≥ 2:

 A language L ⊆ X + is Dn-ps -dependent if and only if there is



(Cn-ps ) a non-empty subset L0 of L with |L0 | ≤ n such that L0 is both

Dp -dependent and Ds -dependent [49].


For all n, L(n+1)-ps ⊆ Ln-ps by definition. In contrast to the hierarchy of

n-codes, which is infinite, the hierarchy of n-ps-codes collapses at n = 4 with
 Codes 41

L4-ps = Lp ∪ Ls . Thus L4-ps ( K∗ . As there are three-element codes which

are neither prefix nor suffix codes, also L3-ps ( L3-code . The class L2-ps has
an alternative characterization by the following condition:

A language L ⊆ X + is Dd -dependent if v = ux = yu for some

½
(Cd )
u, v ∈ L and x, y ∈ X + .

Every 2-ps-code is a 2-code. However, the language {0, 010} is a 2-code, but
not a 2-ps-code. Therefore, L2-ps ( L2-code .
• Between the classes of 3-ps-codes and 2-ps-codes there is another class
of languages, interesting for its combinatorial properties, the class of g-3-ps-
codes:

 A language is Dg-3-ps -dependent if it is D2-ps -dependent or if
(Cg-3-ps ) there are three distinct words u, v, w ∈ L such that {u, v} is
 D -dependent and {v, w} is D -dependent [49].
p s

Thus, a 2-ps-code is a language K ⊆ X + such that every two-element subset

of K is a prefix code or a suffix code. A g-3-ps-code is 2-ps-code K such that,
in every three-element subset of K, at least two elements form a prefix code
or a suffix code.
Every 3-ps-code is the disjoint union of a prefix code and a suffix code;
on the other hand, the union of the prefix code {10, 010} and the suffix
code {0, 1} is not even a 2-ps-code, let alone a 3-ps-code. Moreover, the
language 0+ 1+ is a 2-ps-code which cannot be decomposed into a union of
a prefix code and a suffix code. The classes L3-ps and K∗ are incomparable.
Hence, in general, 3-ps-codes, g-3-ps-codes, or 2-ps-codes need not be codes.
Moreover, L3-ps ( Lg-3-ps ( L2-ps [49].30
The general principles of the constructions of the n-codes and the n-ps-
codes and the reasons as to why the hierarchy does not collapse in the former
case while it does so in the latter are explained in Section 7.
• The class Lb of bifix codes:
½
A language is Db -dependent if it is Dp -dependent or Ds -de-
(Cb )
pendent, that is, Db = Dp ∪ Ds .

Bifix codes are also called biprefix codes in the literature. Their main merit
is that they are both, ω-codes and (−ω)-codes, and that they have some very
interesting mathematical properties (see [4]).
The language K = {01, 10} is a bifix code, but not a ζ-code. For example,
the ζ-message · · · 010101010 · · · has two non-equivalent factorizations over K.
In the general context of information transmission via a noisy channel γ,
the bifix property has the following interpretation – assuming appropriate

30
That the inclusions are proper follows from results discussed in Section 10 below.
42 H. Jürgensen and S. Konstantinidis

synchronization and error correction capabilities: After synchronization, de-

coding can take place, from the point identified by the synchronization, both
to the right and the left without decoding delay – for as long as there are no
errors.
The classes of codes considered so far, have very little – if any – syn-
chronization, error detection, or error correction capabilities in general. As
we move towards codes with additional structure, some of these issues get
addressed.
• There are four basic classes of shuffle codes of index n ( shn -codes) for
n ∈ N: the class Lin of infix-shuffle codes of index n ( in -codes); the class Lon
of outfix-shuffle codes of index n ( on -codes); the class Lpn of prefix-shuffle
codes of index n ( pn -codes); and the class Lsn of suffix-shuffle codes of index
n ( sn -codes) [132], [89], [90], [92], [93].31 The conditions defining these classes
are as follows:
 A language L ⊆ X + is Din -dependent if there are words


(Cin ) u1 , . . . , un , v0 , v1 , . . . , vn ∈ X ∗ such that u = u1 · · · un ∈ L,

v = v0 u1 v1 u2 · · · un vn ∈ L and u 6= v.


 A language L ⊆ X + is Don -dependent if there are words



(Con ) u0 , u1 , . . . , un , v1 , . . . , vn ∈ X ∗ such that u = u0 u1 · · · un ∈ L,

v = u0 v1 u1 · · · vn un ∈ L and u 6= v.


 A language L ⊆ X + is Dpn -dependent if there are words



(Cpn ) u1 , . . . , un , v1 , . . . , vn ∈ X ∗ such that u = u1 · · · un ∈ L,

v = u1 v1 · · · un vn ∈ L and u 6= v.


 A language L ⊆ X + is Dsn -dependent if there are words



(Csn ) u1 , . . . , un , v1 , . . . , vn ∈ X ∗ such that u = u1 · · · un ∈ L,

v = v1 u1 · · · vn un ∈ L and u 6= v.


One has Lp1 = Lp and Ls1 = Ls . The classes Li1 and Lo1 are the classes Li
and Lo of infix codes and outfix codes, respectively [63], [52], [38], [50]. The
corresponding dependences are Di = Di1 and Do = Do1 .
The relation between shuffle codes is shown in Fig. 6.1. Lines indicate
proper inclusions. The language {(0k 1k )n 0k | k ∈ N} is in Lin ∩ Lon , but not
in Lpn+1 ∪ Lsn+1 , and the language {(0k 1k )n | k ∈ N} is in Lpn ∩ Lsn , but not
in Lin ∪ Lon [90]. The language {(01)n 0, 1n } is in Lon , but not in Lin ; the
language {(01)n 0, 0n+1 } is in Lin , but not in Lon ; {1n , (01)n } is in Lpn , but
not in Lsn ; {1n , (10)n } is in Lsn , but not in Lpn . Some further properties
of shuffle codes are mentioned in Section 8 below. Note that L4-ps can be
considered as the largest member of the families of shuffle codes.
The shuffle codes of index n address the following error situation to some
extent: Insertions at up to n positions or deletions at up to n positions cannot
31
The letters i, o, p, and s stand for infix, outfix, prefix, and suffix, respectively.
The classes of shuffle codes have been introduced also under various other names.
 Codes 43

L pn ∪ L s n
..........
..... .........
..... .....
...
...... .....
. .....
..... .....
........ .....
....... .....
.....
...
Lpn .......
..
.
.
.....
... Lsn
.....
..... .........
..... .... ...
..... ..
..... .....
..... .....
..... .........
..........
...
.. Lp ∩ Ls
... n n
...
...
...
...
.. L ∪ L on
..... in
..... .....
........ .........
..
. .... .....
.
.... .....
..... .....
..... .....
..... .....
....... .....
...
Lin .........
..
.... Lon
..... .........
..... . ....
..... ..
..... .....
..... ....
..... .....
..... ........
..........
...
... Li ∩ Lo
... n n
...
...
...
...
.. Lp
......... n+1 ∪ Lsn+1
......... .........
. ...... .....
..
.... .....
..... .....
..... .....
..... .....
........ .....
.....
Lpn+1 ..
. Lsn+1

Fig. 6.1. Relations between the shuffle codes. All inclusions indicated are proper.

turn a code word into another code word. In general, the shuffle codes do
not, however, have useful synchronization capabilities. If synchronization is
not a problem32 then these codes detect up to n bursts of insertions or up to
n bursts of deletions in a code word.
• The class Lh of hypercodes [124], [42], [130]:

A language L ⊆ X + is Dh dependent if it is Din -dependent

½
(Ch )
for some n ∈ N.
S∞
S∞Din ⊆ Din+1 and as n=1 Din is a 3-dependence system, one has Dh =
As
n=1 Din . A mathematically very interesting generalization of hypercodes is
defined and analysed in [104].
Theorem 6.2 Let K ⊆ X + . Each of the following conditions implies that
K is finite.
(a) K is regular and K ∈ Lo .
(b) K is regular and K ∈ Lxn for n ≥ 2 and x ∈ {i, o, p, s}.
(c) K is context-free and K ∈ Lo2 .
(d) K is context-free and K ∈ Lxn for n ≥ 3 and x ∈ {i, o, p, s}.
(e) K is a hypercode.

32
In some applications, synchronization is provided through a separate signal.
44 H. Jürgensen and S. Konstantinidis

Statement (a) is proved in [50] using the Pumping Lemma for regular
languages. Statement (b) follows from Lxn ⊆ Lo . Statement (c) is a con-
sequence of the Pumping Lemma for context-free languages. Statement (d)
follows from Lxn ⊆ Lo2 . For (e), see [123]. This reference contains also
further information about hypercodes.33
• The class Lu of uniform codes (or block codes):

A language L ⊆ X + is Du -dependent if it contains words of

½
(Cu )
different lengths.

Nearly all codes in practical use for error correction or error detection are
uniform codes. Moreover, to enable the construction of such codes with pre-
dictable properties and simple algorithms for coding and decoding, additional
structural properties are assumed. Normally, X is assumed to be a finite field
and the code K is assumed to be a finite-dimensional vector space over X.
See [94] or [99] for further information about uniform codes.
Uniform codes are good at detecting or correcting substitution errors
when synchronization between coder and decoder is not a problem – for
example, in the presence of a common error-free clock signal.
• The classes Lintern of intercodes of index n for n ∈ N [125], [144]:

 A language L ⊆ X + is Dintern -dependent if there are words



(Cintern ) u1 , . . . , un+1 , v1 , . . . , vn ∈ L and w1 , w2 ∈ X + such that

u1 · · · un+1 = w1 v1 · · · vn w2 .


Note that Dintern is a (2n + 2)-dependence. From Dintern+1 ( Dintern it

follows that Lintern ( Lintern+1 . The class Linter1 of intercodes of index 1 is
also known as the class Lcomma-free of comma-free codes. Comma-free codes
are uniformly synchronous bifix codes with synchronization delay 1 for the
noiseless channel.34
In general, if K is an intercode of index n and if, in an error-free message
w over K, n consecutive code words are found then every factorization of w
over K will contain those instances of code words; hence these code words
can be decoded without regard for the rest of the message.
A language K ⊆ X + is said to beS∞an intercode if it is an intercode of index
n for some n ∈ N; hence, Linter = n=1 Lintern is the class of all intercodes.
It is not known whether a dependence system D exists such that Linter
is the class of all D-independent languages inTX + . If so, D would probably
∞
have to be constructed from the intersection n=1 DLintern . The intersection
of dependence systems is, however, not necessarily a dependence system.

33
Parts of Theorem 6.2 have also been proved independently in [89] and [132].
34
The term comma-free refers to the fact that no special synchronization symbol –
a comma – is needed for synchronization without delay. For further information
about intercodes and comma-free codes see [123] and [4].
 Codes 45

Let Q be the class of languages containing only primitive words. Then

Linter is a proper subclass of Lb ∩ Lunif-synch ∩ Q. The language {0, 1101011}
is an intercode (of index 2) which is not an infix code. On the other hand,
one has Linter1 ( Li .
• Note that Q is the set of indepedent sets with respect to the following
dependence system:
A language L ⊆ X + is Dprimitive -dependent if there is a word
½
(Cprimitive )
in L which is not primitive.

• As in the case of K∗ = Lcode , one can also consider the classes Lm-intern
of m-intercodes of index n and the classes Lm-inter of m-intercodes for n, m ∈
N [123]:

 A language L ⊆ X + is Dm-intern -dependent if there is



(Cm-intern ) a subset L0 of L with at most m elements such that L0 is

Dintern -dependent.


 A language L ⊆ X + is Dm-inter -dependent if there is a



(Cm-inter ) subset L0 of L with at most m elements such that L0 is not an

intercode.


Details about the relations between these classes of codes are shown in
Fig. 6.2. Note that L1-inter = Q, that L1-inter is a proper subclass of L2-code ,
and that L2-inter is a proper subclass of Lb ∩ Q. The sets Dm-intern and
Dm-inter are (m + 1)-dependence systems.
• The class Lol-free of overlap-free languages:
A language L ⊆ X + is Dol-free -dependent if there are words
½
(Col-free )
u1 , u2 , u3 ∈ X + such that u1 u2 , u2 u3 ∈ L.

Not every Dol-free -independent set is a code. For example, the language
L = {0, 01, 001} is not a code as (0)(01) = (001), but is overlap-free. As
mentioned in the context of Theorem 3.2, the notion of overlap is crucial for
decoding and synchronization. An instance of a word u ∈ X + found in a
message over an overlap-free language K can never be both, a proper prefix
and a proper suffix of a word in K.
In the literature, a word w ∈ X + is called unbordered if the set {w} is an
overlap-free language.
• The class Lsolid of solid codes:

 A language L ⊆ X + is Dsolid -dependent if it is Di -dependent



(Csolid ) or Dol-free -dependent, that is, Dsolid = Di ∪ Dol-free [126],

[64], [123].


The solid codes are remarkably strong in the presence of errors that result in
loss of synchronization. A detailed discussion of properties of solid codes is
given in Section 11 below.
46 H. Jürgensen and S. Konstantinidis

L2-code •..... . . .
... ..
... ..
... ..
... ..
... ..
... .• ... Lcode = K∗
... ...
... ...
... ...
... ...
L1-inter ...
... L
.
•..... .... .
...
. • b
=Q ...
... .........
....
.....
... ......
... ...........
.
•...........
Q ∩ Lb ...
...
...
...
•...........................
L2-inter .
.
...........
........... L3-inter
.•...........
. . ................
.
........... L4-inter
. . ...........
. .
.
.
.
.
•..........................
........... L5-inter
. . . ...........
. . . ..•
.. . .
. . . . ...
. . . . ...
. . . . ...
L2-inter3 .
•.......................... . .
. . . ...
...
. . . L(2n+1)-inter
. . . ...
.... ...........
........... . L . .
.
... .•............ 3-inter3 . .
. .. .
•. . . . . .
. .
... .... ..................... .
... ... ........... .. L . .
.
...
...
............ 4-inter3 .
...
...
...
...
• .. ..........
... ........... .
.
.
.
...
...
...
........... . .
... ... ... ........... L5-inter . ...
..
... ... ... •.. . . . . . 3 .
...
. . .•
... ... ... ... . .
. ...
....... . . . . .
L2-inter2 •.... ................... .
....
.
....
.
....
.
. . . . ... L inter
.. ...........
........... ... L
. ... ... ... . ...
... .•............ 3-inter2 .... ... . . . .. . . . . .
... ... ................ .. ... . . .•.
... ... ........... .
. . . . . ...
............. L4-inter .. . . ...
... ... .•........ 2 ... .. ...
... ... ..... ...................... . . ... L(2n+1)-intern = . . . = Lintern
... ... ..... ........... ... . .. . . . . .
...... .......... .. .
........... •
... ... .
.. ....
... ... .....
... ... ..
......
. ...
..................
.. ..
L2-inter1 •........................ ... ......... ...........
...........
........... .. ... ........... L5-inter2 = . . . = Linter2
........... ................................
.•....

L3-inter1 = . . . = Linter1

Fig. 6.2. The intercode hierarchy [65].

• The class Lpi of p-infix codes [50]:

A language L ⊆ X + is Dpi -dependent if there are words
½
(Cpi )
u1 ∈ X ∗ , v ∈ L, and u2 ∈ X + such that u1 vu2 ∈ L.
The class Lsi of s-infix codes is defined dually. One has Li = Lpi ∩ Lsi .
The class Lb is incomparable with Lpi and Lsi [50]. A characterization of
the classes of p-infix codes and s-infix codes is given below in the context of
semaphore codes.
• The class Lcircular of circular codes:
 A language L ⊆ X + is Dcircular -dependent if there exist n, m ∈


(Ccircular ) N, and words u0 , u1 , . . . , un−1 , v0 , v1 , . . . , vm−1 ∈ L, w ∈ X +

such that |w| < |v0 | and wu0 u1 · · · un−1 = v0 v1 · · · vm−1 w.


Circular codes were introduced in [78] to investigate synchronization prop-

erties of finite codes. Synchronization is expressed there in terms of finite
self-correcting decoding automata. Such an automaton reads an encoded mes-
sage, received as output of an SID-channel, and computes, as its output, the
decoding. When an error is encountered, the automaton may go through an
incorrect sequence of states; it will, however, reach a correct state – a state
it should reach in the absence of noise – after a bounded number of steps if
no further error occurs.
 Codes 47

Theorem 6.3 [78] Let K ⊆ X + be finite. There is a finite self-correcting

decoding automaton for K if and only if K is a circular code.
This automaton-based approach is used in [78] and also in [97] and [98]
to construct codes that can limit the effect of noise;35 moreover, for a given
memoryless message source, the average code word length of these codes is
nearly minimal.
Corollary 6.1 [107] A finite subset of X + is a circular code if and only if it
is a uniformly synchronous code.
A proof of Corollary 6.1 and several further results concerning circular
codes can be found in [4].
• The class Lprecirc of precircular codes:

A language L ⊆ X + is Dprecirc -independent if, for all



n, m ∈ N, all u0 , . . . , un−1 , v0 , . . . , vm−1 ∈ L, and all s, t ∈ X ∗


(Cprecirc )
 with st = v0 , the equality u0 · · · un−1 = sv1 · · · vm−1 t implies

n = m and ui = vi+hmodn for some h ∈ N0 and all i ∈ n.


Precircular codes are introduced in [19] to study ζ-codes for noiseless chan-
nels. The class Lprecirc is incomparable with K−ω and Kω , it is properly
contained in K∗ and properly contains Kζ and Lcircular . The classes Kζ and
Lcircular are incomparable. For further information about precircular codes,
see also [21].
• The classes Lrsema and Llsema of right semaphore codes and left sema-
phore codes, respectively cannot be defined using dependence systems. A
language K ⊆ X + is a right semaphore code if K is a prefix code such that
X ∗ K ⊆ KX ∗ . By duality, K is a left semaphore code if K is a suffix code
such that KX ∗ ⊆ X ∗ K (see [4], [119], and [123]). One has Lrsema ( Lpi and
Llsema ( Lsi [50].
Any right semaphore code K is a maximal prefix code, that is, not prop-
erly contained in any prefix code. A proper subset K 0 of K is a prefix code,
but not maximal, hence not a right semaphore code. As all subsets of an
independent set are independent, there is no dependence system D such that
Lrsema would be the class of D-independent languages.
Right semaphore codes are interesting for their decoding properties in the
absence of noise. A right semaphore code K has the form X ∗ S \ X ∗ SX +
for some non-empty set S ⊆ X + of right semaphores. In a message over K,
the presence of a right semaphore signals the end of a code word. The error
correction capabilities of right semaphore codes are not known.
Theorem 6.4 [50] A language L ⊆ X + is a p-infix code if and only if it is
a subset of a right semaphore code; it is an s-infix code if and only if it is a
subset of a left semaphore code.

35
See also [96].
48 H. Jürgensen and S. Konstantinidis

Thus, the class Lpi of p-infix codes is the smallest class of languages which
can be defined by a dependence system and contains the class Lrsema of right
semaphore codes. By duality, Lsi is the smallest class of languages which can
be defined by a dependence system and contains Llsema .
Theorem 6.5 [39] A language L ⊆ X + is an infix code if and only if it is
the intersection of a right semaphore code with a left semaphore code.
• The class Lrefl of reflective codes is defined as follows: A language
K ⊆ X + is reflective if, for every u, v ∈ X ∗ with uv ∈ K, one has vu ∈ K.
A reflective code is a language which is reflective and a code [106]. The class
Lrefl is a proper subset of the class of Li of infix codes. As a subset of a
reflective code is not necessarily reflective, the class of reflective codes cannot
be defined by a dependence system.
Many more classes of codes are considered in the literature – with mo-
tivation ranging from purely combinatorial questions to special concerns in
information transmission. The classes introduced in this section are meant
to serve as paradigms for typical constructions and typical questions.

7. A hierarchy of classes of codes

One of the questions to be raised when one introduces a new class of codes or
applies some construction – like the n-code construction – to existing classes
of codes is where the new classes are located with respect to the known classes.
The theory of dependence systems provides an elegant general framework for
dealing with such questions. The required tools are explained in this section.
Before elaborating on the details, we show the relation among the classes
of codes or languages introduced in Section 6. In Fig. 7.2, we show the global
situation. Details of the hierarchies of shuffle codes and intercodes are shown
in Fig. 6.1 and Fig. 6.2, respectively. Some further inclusions between classes
of codes are summarized in the next theorem.
Theorem 7.1 The inclusions among the classes Lunif-synch , Kζ , Lldecodable ,
Lrdecodable , Lcircular , K−ω , Kω , Lprecirc , and K∗ as shown in Fig. 7.1 are valid
and are the only valid ones among these classes.
Proof: The inclusions Kζ ( Kω ( K∗ and Kζ ( K−ω ( K∗ are proved as
Proposition 3.1 (see [21], [128], and [20]). For the inclusions

Lunif-synch ( Lrdecodable , Lunif-synch ( Lldecodable , and Lunif-synch ( Lcircular

see [4]. By [128],

Lrdecodable ( Kω and Lldecodable ( K−ω .

By [21],
Lcircular ( Lprecirc ( K∗ and Kζ ( Lprecirc .
 Codes 49

K∗
.......•.......................................
.........
....... ....... ..............
....... .......
..
........... ....... .........................
.. ....... .............
....... ....... .............
.. .
... ....... .......
....... .............
.............
.
....... ....... .............
.......
. ....... ...........
K −ω •.... ............
. ..
.. .....•
.. .. K
ω ......• . Lprecirc
. .. . ............. ....
....
.......
....... .............. .
.
.
. ...... ................... ...
....... .......
. . .............. ...
... ....... . ..... ...
....
.
.
.......... ......
.
...
... ....... ..... ........
...
.......
....... . .... ..... .....................
. .
.
. .....
... ....... ................................ .
.
. ...
........................ . L
Lldecodable •...................
. ...
ζ •.........
.
.
..
....• rdecodable................• Lcircular
.
.
. ...
.
..........
.......... K .....
...... ..
......
......................
.
.......... ..... ..... ..........
.......... ..... ..... ..........
.......... .. ..... ..........
..........
.......... ........ ..... ..........
.......... ..... ............................
......................
•
Lunif-synch

Fig. 7.1. Inclusions for Theorem 7.1. Lines indicate proper inclusion. The diagram
does not indicate intersections or unions.

By Theorem 4.6, Lunif-synch ( Kζ . It remains to prove that no other inclu-

sions exist.
Consider the following seven codes:

K0 = {00}, K1 = {01, 10},

K2 = {0, 01, 11}, K3 = {0, 10, 11},
n n+1
K4 = {01} ∪ {01 01 | n ∈ N}, K5 = {10} ∪ {1n+1 01n 0 | n ∈ N}.

By [21],
K1 ∈ (K−ω ∩ Kω ) \ Lprecirc and K2 ∈ Lprecirc \ Kω ,
hence K3 ∈ Lprecirc \ K−ω . Therefore, Lprecirc is incomparable with Kω and
K−ω [21]. By Example 3.1(4), Kω and K−ω are incomparable. By the same
example, also Lldecodable and Lrdecodable are incomparable. Moreover,

K2 ∈ Lprecirc \ Lrdecodable , K3 ∈ Lprecirc \ Lldecodable ,

and
K1 ∈ (Lrdecodable ∩ Lldecodable ) \ Lprecirc .
Thus, Lprecirc is incomparable with Lldecodable and Lrdecodable . One has

K0 ∈ (Kω ∩ K−ω ) \ Lcircular , K4 ∈ Lcircular \ Kω ,

and
K5 ∈ Lcircular \ K−ω .
Hence, Lcircular is incomparable with Kω and K−ω . Moreover,

K0 ∈ Kζ \ Lcircular and K4 ∈ Lcircular \ Kζ .

Thus, Kζ and Lcircular are incomparable. The incomparability of K ω and

K−ω implies that Kω 6⊆ Lldecodable K−ω 6⊆ Lrdecodable ; by Example 3.1(4),
50 H. Jürgensen and S. Konstantinidis

6 K−ω . Hence, Lldecodable and

Lldecodable 6⊆ Kω and, by duality, Lrdecodable ⊆
K are incomparable and, dually, Lrdecodable and K−ω are incomparable. As
ω

K0 ∈ (Lldecodable ∩ Lrdecodable ) \ Lcircular

and Lcircular is incomparable with Kω and K−ω , Lcircular is also incomparable

with Lldecodable and Lrdecodable . Finally,

K1 ∈ Lrdecodable \ Kζ

while the code

K = {010, 20} ∪ 2(001)∗
used in the proof of Theorem 4.6 is in Lrdecodable , but not in Kζ ; hence,
Lrdecodable and Kζ are incomparable. By duality also Lldecodable and Kζ are
incomparable. ¤
Many of the classes of codes introduced in Section 6 can also be defined
using partial order relations. For example, for u, v ∈ X + , let u ≤p v if u
is a prefix of v. A language K ⊆ X + is a prefix code if and only if, for
any two words u, v ∈ K, u ≤p v implies u = v, that is, if and only if K
is an anti-chain with respect to the order ≤p . Similar characterizations by
partial orders exist for many other natural classes of codes; for some classes
of codes, for instance the outfix codes, this type of characterization requires
a binary relation, which is not a partial order, however. Moreover, in some
cases no such characterizations seem to exist while, on the other hand, there
are also partial orders on X + – even very natural ones – that lead to classes
of languages which are not codes. A summary of most of the research on this
approach to the characterization of classes of codes is given in [123]. In an
attempt to clarify the underlying principles and to unify the presentation,
this approach is extended to a certain very general class of finitary relations
in [65]. From that work, one can draw the following three observations: First,
many of the properties of code constructions – like building of hierarchies or
their collapse – are nearly unrelated to the structure of X + and are simply
consequences of properties of the abstract construction method itself; second,
the specific property of relations – being sets of tuples – are not used at all; 36
third, the key notion in all constructions is that of independence as their
principal abstract properties can be derived already at this level of generality.
Dependence theory serves as an appropriate general tool: While, of course,
it cannot solve all problems, it can, however, help to clarify their structure
and to expose essential properties. In the sequel we show a few applications
of this approach.

36
Thus, while it may be quite interesting, in applications of prefix codes and in
proofs concerning prefix codes, to know that ≤p is a partial order, this fact itself
is not essential for the construction.
 Codes 51

......... 2-code
L
....•
........ .... ................
........ ........
........ .... ........
............... ... ........
. ........
........ ... ........
..... .......... .
. ........
........
..... .
..... •
.
. L3-code
.... .. ... .. ........
....
........ ... ... . ........
........
. .. .
. ....... ..... ....... .
. ........
.... .
. . ..... .... ........ . ........
........
... .. .. ..... ..... ....... . ........
..
. ...... .... ..... . ........
L2-ps ............. ...
. .
.. .....
. ... .
.
........
......
•... ...........
. .. . n-codes •.... L1-inter = Q
... .... ........ .
. ...
.
. . . .......... . ....
Lg-3-ps •.... ... . .... ....... .
. ...
... ............... . ∗ ...
............. . L = K ...
L3-ps .................. • ........
... . .
..... ... . . ...•.... code ...
...
..... .. . ..
........
........ . ..... ....... .
... .....
........ ...... ...
........ ....... ..... ..
.
. ...
........ .... ..
........ ............... . ....
L4-ps.........• ............
. • . .
......Lprecirc ...
..
... ..... ........ ..
. ...
. ..... ...... .. .
. ........
.....
.. ...
. ....... . ..... ...
.. .
. ........... .. .
... . ... ..... .....
.....
.. ...
............ ........
....
.....
....... .....
.. ...... ........
... . . . .. ...
Lp....•...................
.
..... .. . . . . . .
..•
.... L
.. ... s
.
•.....L
..
..... circular ...
... ........ ..... .. . . ... ....
..
. ........
.. ........... . .... .....
.
. ...
. ........ ..... . . ... .....
... ..
. ........ ....... . . ..
. ...
.. .
.
........
. . ........... . ...
.
.....
.. ...
.. . ........ .. ...... . .... ..... ...
. . ...
.................... .... ..
......
Lpi •....................... L • .. .....................................................
. ......
. .... • .
......................................................si L • . L
..... unif-synch
. ...
.. . ......... b ... .
. .. ...... . ... .......................................... ..... . ....
... . ........
........ . ....... . ..... .. . ... .. ............. ....................................................
. .... .. .. .. .
... . ........ Li ∪ Lo.....• ........ ....... .. .... .... . ... ...... • . Q ∩ Lb
... .. ........
........ .... ...
.. .... .. .. ...... .
. ... . ....... .....
... . ........ ....................................... . ... ..... ...
... . ............. ... ..... ...
... .. L •
...........
.
i.. . ........
•
. L o
. ..
. .
.
.
.....
..... ...
... . . . .
. .. ...
. .
... . .. .. ........... .. . ... .....
. ...
L
... .. .
.
.. .. .......
........
.
.
.
.
.
...
.
.....
...... .
. .. .
• . 2-inter
... . ... . . .. . .. .
.. . . ........... . .. . ..... . . ..
... . . ...... . .
.. ..
...... . .
... .. ..
. . .
...... . . . . . .
... . ...
. . ...... . .. . ........ . .
. . ...... . .. .. ..... . ..
... . ... . . ...... . .. .....
... .. ... . . ...... . .... .
. • .
.
.
... ..
. ...... . ... . . .
. ...... . ... .
...
...
.
. .
.
..
. ...... .
....... .... .
. .
. Linter ...
...
.
. ..
.
. shuffle codes .
. ....... ..
. . .
. .
.
.
.
... . ... . .............. . .
...
.
. ... . .
. .. ........ .. ..
.. . ... ...... . .
... .
. . . .
.
.... .. ...... .
n-intercodes .
... . ... . . ........ .
. ..
... . ... . . ... ...... . .
...
.
. ....
.. ..
.
. .
.
. .
.
...
......
......
..
.
(of index m) .
..
... . .
........
... ...... .. ..... ...... .
..
.
... ...
.
. .. .... ...... . ..
. ...... . .
... ... . . .. .. ...... .. .
..
... .. ...
. . . . ..
. ......
...... . .
. .
... ... .. .
..
.. ...... .. . .
... ... .. .
. .. ..... ...... .
...... .
.
. ..
... ... .. . .. ... ...... . . .
.
... ... . ..
.
. . .. .......
....... . .
.
... .. . ..... ....... .. . .
.. .. . ..
... ... . . .. . ...... . .
Lrsema •.. •.. Lrefl Lh. •..................... •... Llsema ......
•.... Linter1 =
.......
... ....... ....
.... .......
....... ... Lcomma-free
.... ....... ...
... .......
....... ...
Lu •.............. . ....... .
.... . ...•... L
.......
.......
... ........
. .. .. solid
....... .. .
... .
....... ....... ...........
.......
.......
.......
....... .
. ........ ...........
..
....... ....... ...........
....... ....... ...........
....... .........................
.......
....... •...
....... .
.... L ∩ L
....... h solid
.......
....... ....
....... ....
....... ..
......
Lu ∩ Lsolid •

Fig. 7.2. The classes of languages introduced in Section 6. Lines indicate (known)
proper inclusions; dotted lines indicate hierarchies. The diagram does not, in gen-
eral, indicate intersections or unions.

As a preparation for the exploration of the hierarchies of codes we re-

view a few simple properties of dependence and n-dependence systems. For
this purpose, let S be an arbitrary, but fixed non-empty set. The following
statement is an immediate consequence of the definitions.
Remark 7.1 If D1 and D2 are dependence systems on a set S and D1 ⊆ D2
then LD2 ⊆ LD1 , that is, every D2 -independent set is D1 -independent. A set
52 H. Jürgensen and S. Konstantinidis

is both D1 -independent and D2 -independent if and only it is (D1 ∪ D2 )-in-

dependent, that is, LD1 ∩ LD2 = LD1 ∪D2 .
For a family D of dependence systems, let
\ \ ^ ^ [
D= D and D= D= D.
D∈D D∈D D
T
D∈D(S),D⊆

V
By Remark 6.1, DTis a dependence system; it is the largest dependence
system contained in D. Similarly, if D is a family of n-dependence systems
then ^ [
n D = D
D∈D(n) (S),D⊆ D
T

is an
T n-dependence system, hence the largest n-dependence system contained
in D.
Lemma 7.1 [66] For n ∈ Nℵ0 , the algebra (D(n) , ∧
n , ∪) is a complete lattice

with ∅ as the minimum and 2S6=∅ as the maximum.

For every L ⊆ 2S and n ∈ Nℵ0 , let

Ψn (L) = {D | D ∈ D(n) (S), L ⊆ LD }

ψn (L) = {D | D ∈ D(n) (S), LD ⊆ L}
and
(n)
[
DL = D.
D∈D(n) (S),L⊆LD

(n)
Again, when n = ℵ0 , we usually omit n. By Lemma 7.1, DL is well-defined
as the maximal n-dependence D system such that all L ∈ L are D-inde-
(n)
pendent. If L = LD for some n-dependence system D then D = DL and
LD(n) = L.
L

Lemma 7.2 [66] Let S be a non-empty set, L ⊆ 2S , and n, m ∈ Nℵ0 with

(n) (m) (m) (n)
n < m. Then DL ⊆ DL . Moreover, if L = LD(n) then DL = DL and,
L
therefore, L = LD(m) .
L

A set L ⊆ 2S is said to be Subn -determined, with n ∈ Nℵ0 if it satisfies

the following condition: L ∈ L if and only if Subn L ⊆ L. If m ∈ Nℵ0 , n ≤ m,
and if L is Subn -determined then L is also Subm -determined.
The class K∗ , for example, is Subℵ0 -determined: A language K is a code
if and only if every finite subset of K is a code. Most classes of codes in-
troduced so far are Subn -determined for some n ∈ Nℵ0 . The classes Lrsema
and Llsema are not Subn -determined for any n as they are not closed under
taking subsets.
 Codes 53

For an arbitrary set D ⊆ 2S6=∅ , let compl(D) be the set of all subsets L of
S such that L0 ⊆ L for some L0 ∈ D. We say that compl(D) is the completion
of D. For n ∈ Nℵ0 and L ⊆ 2S , one has

(n)
DL ⊆ compl({L | L ∈
/ L, 0 < |L| < n})

with equality if L ∈ L(n) (S).

For n ∈ Nℵ0 , the n-support of a set D ⊆ 2S6=∅ is the set supportn (D) =
D ∩ Subn S. In general, compl(supportn (D)) ⊆ D with equality when D is
an n-dependence system.
For example, support3 (Dp ) is the set of all two-element sets {x, y} of
words x, y ∈ X + such that x is a proper prefix of y. Moreover, Dp =
compl(support3 (Dp )).
In general, if D is a set of non-empty subsets of S of cardinality strictly
less than n, then compl(D) is an n-dependence system.
Theorem 7.2 [66] Let S be a non-empty set, let L ⊆ 2S , and let n ∈ Nℵ0 .
The following properties obtain:
(a) (Ψn (L), ∧
n , ∪) is a complete lattice. Hence it has a unique maximum and

minimum.
(b) ψn (L) is a ∪-complete ∪-semilattice. Hence, it has a unique maximum.
Moreover, if L is Subℵ0 -determined then one has:
(n)
(c) DL = compl({L | L ∈ / L, 0 < |L| < n}), and this is the maximum of
Ψn (L).
(d) For every D ∈ ψn (L), there is a minimal D∞ ∈ ψn (L) with D∞ ⊆ D.
This statement relies on Zorn’s Lemma.
(e) There is an n-dependence system D such that L = LD if and only
if ψn (L) has a minimum; moreover, in this case, D = min ψn (L) =
max Ψn (L).
As a consequence of Theorem 7.2 one derives the following Gap Theorem;
it states a condition under which a class of languages will not be characteri-
zable by any n-dependence system.
Theorem 7.3 [66] Let S be a non-empty set, let n ∈ Nℵ0 , and let L, L1 ⊆ 2S .
If L ⊆ L1 ( LD(n) then there is no n-dependence system D with L1 = LD .
L

Note that, in Theorem 7.3, it is not excluded that L = L1 . We show an

application of Theorem 7.3 to the hierarchy of n-codes. To unify the notation,
we refer to the class K∗ = Lcode of codes as the class Ln-code of n-codes for
n = ℵ0 .
Theorem 7.4 Let n, m ∈ Nℵ0 with n < m. There is no (n + 1)-dependence
system D with Lm-code = LD .
54 H. Jürgensen and S. Konstantinidis

Proof: As the class Lcode is Subℵ0 -determined, one has

(n+1)
DLcode = compl({L | L ∈
/ Lcode , 0 < |L| < n + 1})

by Theorem 7.2(c). Hence, LD(n+1) = Ln-code . By [51],

Lcode

Lcode ⊆ Lm-code ( Ln-code .

By Theorem 7.3, there is no (n+1)-dependence system characterizing Lm-code .

¤

For the special case of m = ℵ0 , Theorem 7.4 states that the class of
codes cannot be characterized by any n-dependence system with n finite.
Theorem 7.4 is based on a similar result of [65] which, however, is stated there
in terms of finitary relations. It strengthens various non-characterizability
results for the classes of codes by binary relations (see [123]). Moreover, its
proof clearly separates language theoretic from structural issues.
The constructions used for the classes of languages shown in Fig. 7.2
follow three different patterns:
(1) An infinite or finite strictly increasing sequence of n-dependence systems
D1 ( D2 ( · · ·, for a fixed n ∈ Nℵ0 , is used to define a strictly
T decreasing
sequence of classes of codes LD1 ) LD2 ) · · ·. TheSlimit LDi exists
and is the class of independent sets with respect to Di .
The hierarchy of shuffle codes is obtained by a construction of this
kind for n = 3. It starts with the 4-ps-codes and ends with the hyper-
codes.
(2) Starting from a dependence system D and the corresponding class LD
of D-independent sets, one considers the n-dependence systems Dn =
compl(supportn (D)) derived from D and the resulting classes LDn of
Dn -independent sets, where n ∈ Nℵ0 .
This is the construction used in the case of the n-codes and of the
m-intercodes of index n – for fixed n and varying m in the latter case.
A variant of this construction starts with several dependence systems
as in the case of the n-ps-codes of [49] or the n-infix-outfix codes of [91].
(3) An infinite or finite strictly decreasing sequence of dependence systems
D1 ) D2 ) · · · is used to define a strictly increasing sequence of classes
of codes LD1 ( LD2 ( · · ·.
This is the construction used in the case of the intercodes of index n
and, with m varying, for m-intercodes of index n.
Construction method (1) can be purely language theoretic and, thus, outside
the realm of the structural analysis tools provided by dependence theory.
Similarly, construction method (3) may have very few properties permitting
a structural analysis. In either case, this depends very much on the specific
sequences of dependence systems. On the other hand, method (2) turns out
 Codes 55

to depend very little on language theoretic specifics. This issue is explored

further in the rest of this section. Again, the main results can be proved
without using any properties of X + .
S
Consider a family L of families of subsets of S, that is, L ⊂ 22 . For
m ∈ Nℵ0 , let Lm,L be the family of subsets of S defined by
[
L ∈ Lm,L , if and only if, for all L0 ⊆ L, |L0 | < m implies L0 ∈ L.
L∈L

When D is a class of dependence systems, to simplify the notation, we write

Lm,D instead of Lm,{LD |D∈D} .
For m = 1, one has
½ S
∅, if ∅ ∈
/ L∈L L,
L1,L =
2S , otherwise.

In the sequel, we assume without special mention that m > 1.

Example 7.1 Let L = {Lp , Ls }. Then Ln+1,L is the class Ln-ps of n-ps-codes
introduced in [49]. Note that, in this case,

L5+i,L = Lp ∪ Ls = L4-ps ( L4,L = L3-ps ( L3,L = L2-ps

for all i ≥ 0. In a similar fashion, one defines the class of n-infix-outfix

codes [91]. The classes of n-codes are also obtained in this way using L =
{Lcode }.

We now determine how the construction of Lm,L depends on the param-

eters m and L.
S
Proposition 7.1 [66] Let m, n ∈ Nℵ0 and let L ⊆ 22 . If m ≤ n then
Ln,L ⊆ Lm,L .

By Proposition 7.1, a change in the parameter m in the construction Lm,L

may lead to a hierarchy. Further below we establish criteria as to when this
hierarchy collapses.

Proposition 7.2 [66] Let I be a non-empty set, let m ∈ Nℵ0 , and, for i ∈ I,
S
let mi ∈ Nℵ0 and Li ⊆ 22 . If m ≤ mi for all i ∈ I then i∈I Lmi ,Li ⊆
S
Lm,Si∈I Li .

To illustrate Proposition 7.2, consider I =S{1, 2} with L1 = {Lp } and

L2 = {Ls }, and let m = m1 = m2 = 3. Then i∈I L3,Li = Lp ∪ Ls = L4-ps
while L3,Si∈I Li = L2-ps is a proper superset.
56 H. Jürgensen and S. Konstantinidis

Theorem 7.5 [66] Let m ∈ Nℵ0 , let I be an arbitrary non-empty set and,
for i ∈ I, let Di be an ni -dependence system where ni ∈ Nℵ0 . Let D = {Di |
i ∈ I}. The following statements hold true:
(a) Lm,D ⊆ Lm,{Vi∈I Di } .
P
(b) If I and each ni is finite and m > i∈I ni − |I| then
[
Lm,D = Lni ,{Di } .
i∈I

By Theorem 7.5(b), the sequence

L2,D ⊇ L3,D ⊇ · · · ⊇ Lm,D ⊇ Lm+1,D ⊇ · · ·

stabilizes no later than at Lm,D if D = {Di | i ∈ I} is P a finite family of

ni -dependence systems Di with each
S n i finite, where m = i∈I ni − |I| + 1.
Moreover, in this case Lm,D = i∈I LDi . The sequence may, of course,
stabilize earlier than that.
Example 7.2 As in Example 7.1, let L = {Lp , Ls }. Both Lp and Ls can be
characterized by a 3-dependence system. Hence, L5+j,L = Lp ∪ Ls for all
j ≥ 0. For the same reason, with L = {Li , Lo }, L5+j,L = Li ∪ Lo for all
j ≥ 0.
The point of Theorem 7.5 and Example 7.2 is that the collapse of the
hierarchy construction Lm,D is not a language theoretic phenomenon at all;
it is solely a matter of dependence theory.
Theorem 7.6 [66] The following statements hold true:
S
(a) Let D be a family of dependence systems S on S such that D∈D LD is
Subℵ0 -determined. Then limm→∞ Lm,D = D∈D LD .
(b) Let D be a dependence system on S such that LD 6= LD0 for every n-de-
pendence system D 0 with n < ℵ0 . Then there are infinitely many proper
inclusions in the sequence L2,{D} ⊇ L3,{D} ⊇ · · ·.
S
Generalizing Theorem 7.5(b), D∈D LD always is an upper bound for
limm→∞ Lm,D which is achieved if the former is Subℵ0 -determined. Theo-
rem 7.6(b) complements Theorem 7.3 in the following sense: Theorem 7.3
permits one to show that a class of languages cannot be characterized by any
n-dependence system, but requires the knowledge about the proper inclusion
of the language classes involved; Theorem 7.6(b) permits one to show that
inclusions are proper, given that non-characterizability properties have been
established.
To conclude this section, we consider the classes of m-intercodes of index
n. The intercodes of index n can be defined using (2n + 2)-dependence
systems. One has Lm-intern = Lm+1,{Lintern } and, therefore, by Theorem 7.5,
that the hierarchy Lm-intern , for fixed n and varying m, stabilizes at m =
 Codes 57

2n+1 as shown in Fig. 6.2. Previous proofs of this hierarchy collapse use fairly
involved language theoretic arguments; Theorem 7.5 provides a tool which
is independent of language theory. On the other hand, language theoretic
arguments are definitely needed to prove that the inclusions prior to the
predicted collapse are proper.

8. The syntactic monoid of a code

The syntactic monoid of a language often reveals certain combinatorial prop-
erties of the language in algebraic terms. In the theory of codes, two types
of syntactic monoids are usually considered, the syntactic monoid of the
code itself and the syntactic monoid of the set of all ∗-words over the code.
Some important results concerning the latter type are presented in [4], [123],
and [71]. In this section we focus on less known work concerning the former
type.
Recall that a semigroup is a non-empty set, M say, equipped with an
associative multiplication; M is a monoid if it is a semigroup with an identity
element, that is, an element 1M such that 1M x = x = x1M for all x ∈ M .
An element y ∈ M is said to be a zero element of M if xy = y = yx for all
x ∈ M ; in this case we write 0M instead of y. A non-empty subset N of M
is an ideal if N M ∪ M N ⊆ N .
Now assume that M is a monoid with zero element and |M | ≥ 2, hence
1M 6= 0M . Clearly {0M } is an ideal of M and is equal to the intersection of all
ideals of M . The intersection of all ideals of M which are different from {0M }
– if this intersection is different from {0M } – is called the core of M , denoted
by core(M ). An element c ∈ M is called an annihilator if cx = xc = 0M for
all x ∈ M \ {1M }. Let annihil(M ) be the set of all annihilators of M .
Let M be a monoid and L ⊆ M . Let PL ⊆ M × M be the relation on M
consisting of all the pairs (u, v) ∈ M ×M such that, for all x, y ∈ M , xuy ∈ L
if and only if xvy ∈ L. The relation PL is called the principal congruence
of L – it is indeed a congruence. Instead of (u, v) ∈ PL we write u ≡ v(PL )
in the sequel. The set L is said to be disjunctive in M if PL is the equality
relation. The set WL = {u | u ∈ M ∧ M uM ∩ L = ∅} is called the residue of
L. If WL 6= ∅ then WL is an ideal of M . If L is a singleton set, L = {c}, we
often write c instead of {c}; thus c being disjunctive means {c} is disjunctive,
Pc = P{c} , and Wc = W{c} .
For x ∈ M , let x/PL denote the PL -class of x; this notation is extended to
subsets of M in the natural fashion. Note that L is a union of PL classes. The
multiplication on M induces a multiplication on M/PL via (x/PL )(y/PL ) =
(xy)/PL , and M/PL is a monoid with 1M /PL as identity element. The
mapping σL of M onto M/PL given by σL (x) = x/PL is a morphism and the
set L/PL is disjunctive in M/PL .
When M = X ∗ for an alphabet X then PL is also referred to as the
syntactic congruence of L and the factor monoid syn L = X ∗ /PL is the
syntactic monoid of L. A language L is regular if and only if syn L is finite.
58 H. Jürgensen and S. Konstantinidis

The morphism σL of X ∗ onto syn L is called the syntactic morphism of L. For

general information about syntactic monoids of languages see [71] and [24].
Example 8.1 Let X = {0, 1, 2} and L = {0n 1n 2n | n ∈ N}. The set L is
an infix code which is not regular, hence syn L is infinite. The residue of
L is non-empty; for instance, 021 ∈ WL . In general, when the residue of a
set is non-empty then it is a congruence class with respect to the principal
congruence and it is the zero element of the factor monoid. Thus, syn L has
a zero element 0 and 0 = WL /PL .
The set {λ} is also a PL -class; therefore, the identity element 1 of syn L
is λ/PL = {λ} and syn L \ {1} is a subsemigroup of syn L.
If u ∈ L then xuy ∈ L if and only if x = y = λ. Therefore, also L is a
PL -class; let c = L/PL . Then 1 6= c 6= 0 and c is a disjunctive element of
syn L. Moreover, c = xcy implies x = y = 1. If u ∈ L and v ∈ X + then
uv, vu ∈ WL . Thus, c ∈ annihil(syn L).
If N is any ideal of syn L and N 6= {0} then {b, 0} ⊆ N for some b 6= 0.
Let v ∈ X ∗ be such that v/PL = b. Then v ∈ / WL and there are x, y ∈ X ∗
such that xvy ∈ L. Thus, (x/PL )b(y/PL ) = c and, as N is an ideal, also
c ∈ N . Thus syn L has a core and c is an element of it.
It is shown in [101] that the properties derived in Example 8.1 are char-
acteristic of syntactic monoids of infix codes in general. Among these, the
property that c = xcy implies x = y = 1, where c = L/PL , can be viewed as
a way of describing Di -independence in terms of the elements of syn L. This
observation leads to a general treatment of syntactic monoids of codes which
is based on abstract formal properties of the predicates defining dependence
systems [54]. We outline the main ideas and results of this approach. As a
general framework we use the category of pointed monoids.
A pointed monoid 37 is a pair (M, L) where M is a monoid and L is a
subset of M . Let (M, L) and (M 0 , L0 ) be pointed monoids. A pointed-monoid
morphism of (M, L) into (M 0 , L0 ) is a semigroup morphism ϕ of M into M 0
such that ϕ−1 (L0 ) = L. Such a pointed-monoid morphism ϕ is surjective (or
onto), injective, bijective if it is so as a semigroup morphism of M into M 0 ;
it is non-erasing if ϕ−1 (1M 0 ) = {1M }. Let P denote the category of pointed
monoids. A predicate P on P is said to be invariant if, for any pointed
monoid (M, L), P satisfies the following conditions:
• For any surjective pointed-monoid morphism ϕ of (M, L), P is true on
(ϕ(M ), ϕ(L)) if P is true on (M, L).
• For any surjective non-erasing pointed-monoid morphism ϕ of (M, L), P
is true on (M, L) if it is true on (ϕ(M ), ϕ(L)).
Proposition 8.1 Let P be an invariant predicate on P and let LP be the
class of languages L over X for which P is true on (X ∗ , L). The following
statements are true:
37
Called p-monoid in [113].
 Codes 59

(1) If σL is non-erasing then L ∈ LP if and only if P is true on the pointed

monoid (syn L, σL (L)).
(2) If P is decidable on finite pointed monoids, L is (constructively) regular,
and σL is non-erasing, then it is decidable whether L ∈ LP .
Proof: The first claim is just a restatement of the definition of invariance.
For the second claim, if L is constructively given as a regular language then
one can compute the syntactic monoid syn L and the set σL (L). Note that
σL is a pointed-monoid morphism. The fact that L is regular implies that
syn L is finite. Therefore, P is decidable on (syn L, σL (L)). The invariance
of P implies that it is decidable whether L ∈ LP . ¤

To apply Proposition 8.1 to a given predicate P , one has to establish that

P is invariant and decidable on finite pointed monoids. In the rest of this
section we focus on predicates on P which express independence conditions
in the form of implications as follows. Let V be a set of variable symbols
(for monoid elements), and let Λ be a set variable symbol (for subsets of
monoids). We consider quantifier formulæ of the form
¡ ¢
hquantifier prefixi hformulai −→ hformulai

in which the quantifier prefix and the formulæ satisfy the following conditions:
• The quantifier prefix involves only universal quantifiers, one for each vari-
able in V actually used.38
• The formulæ are disjunctions of conjunctions of equations and inclusions.
An equation has the form u = v and an inclusion has the form u ∈ Λ,
where u, v ∈ V ∗ ∪ {1}. We refer to the first formula as the premiss and to
the second one as the conclusion.
For lack of a better term, such implications are called basic implicational
conditions.
Definition 8.1 An implicational condition is a conjunction of basic implica-
tional conditions. If I is an implicational condition and (M, L) is a pointed
monoid, then (M, L) is said to satisfy I if I is true on M for Λ = L.
In Table 8.1 we show implicational conditions for some of the language
classes defined in Section 6; in the sequel, we refer to these conditions by the
names assigned to them in that table.
There is a similarity between implicational conditions as introduced and
implications used to define implicationally defined classes or quasivarieties
of algebras (see [100]); the difference is that disjunctions and inclusions are
permitted in our implicational conditions. The full meaning of this similarity
is not known.

38
In a more general setting, quantification over the number of variables and re-
strictions on the domains of variables are also useful [54].
60 H. Jürgensen and S. Konstantinidis

Table 8.1. Implicational conditions for some of the language classes introduced in
Section 6.

Family Name Implicational condition

`
∀u, v (u ∈ Λ ∧ v ∈ Λ ∧ uv = vu)
Lac = L2-code Iac ´
→u=v
`
∀u, x, y (u ∈ Λ ∧ ux ∈ Λ ∧ yu ∈ Λ
Ld = L2-ps Id ´
∧ ux = yu) → x = y = 1
∀x1 , . . . , xn , y1 , . . . , yn
`
(x1 · · · xn ∈ Λ
L pn I pn
∧ x1 y1 x2 y2 · · · xn yn ∈ Λ)
´
→ y1 = · · · = y n = 1
L i n , L on , L s n I i n , I on , I s n analogous to Lpn
L pn ∩ L s n Ipn ,sn I pn ∧ I s n
Lb Ib see Lpn ∩ Lsn for n = 1
L i n ∩ L on Iin ,on I i n ∧ I on
` ´
Lpi Ipi ∀u, x, y (u ∈ Λ ∧ xuy ∈ Λ) → y = 1
Lsi Isi analogous to Lpi
∀u1 , . . . , un+1 , v1 , . . . , vn , x, y
`
(u1 ∈ Λ ∧ · · · ∧ un+1 ∈ Λ
∧ v1 ∈ Λ ∧ · · · ∧ v n ∈ Λ
Lintern Iintern
∧ u1 · · · un+1 = xv1 · · · vn y)
→ ((x = 1 ∧ y = un+1 )
´
∨ (x = u1 ∧ y = 1))
`
∀x, y, z (xy ∈ Λ ∧ yz ∈ Λ)
Lol-free Iol-free ´
→ (x = 1 ∨ z = 1 ∨ y = 1)
Lsolid Isolid Ii ∧ Iol-free

The families Lcode , Ln-code for n > 2, Lm-inter , Linter , Q, Lrsema , Llsema ,
and Lh , Lu are not listed in Table 8.1; it seems that some of these cannot be
characterized with implicational conditions as they seem to require existential
quantifiers or quantification over the number of variables. For example, Lh
would be defined by

Ih = ∀n∀x0 , . . . , xn , y1 , . . . , yn
¡ ¢
(x0 · · · xn ∈ Λ ∧ x0 y1 x1 y2 · · · yn xn ∈ Λ) → y1 = · · · = yn = 1 .

The classes L4-ps , L3-ps , Lg-3-ps , and Lm-intern are not listed either; they do,
however, have characterizations by implicational conditions, albeit rather
complicated ones.
 Codes 61

Proposition 8.2 [54] The predicates Ipn , Iin , Ion , Isn , Ipn ,sn , Iin ,on , Ipi , Isi ,
Ih , and Isolid are invariant.
Proof idea: Each of the predicates satisfies the following simple conditions:
(1) For any pointed monoid (M, L) and any surjective pointed-monoid mor-
phism ϕ of (M, L), if a premiss is false for some assignment of values in
M to the variables then that premiss is also false for the corresponding
assignment in ϕ(M ).
(2) For any pointed monoid (M, L) and any surjective non-erasing pointed-
monoid morphism ϕ of (M, L), if a conclusion is false for some assignment
of values in M to the variables then that conclusion is also false for the
corresponding assignment in ϕ(M ).
These conditions are sufficient for an implicational condition (even involving
quantification over the number of variables) to be invariant. All the pred-
icates listed satisfy (1) and (2). This is true because the premisses involve
only inclusions and the equations involved in the conclusions are of the form
x = 1. ¤

Note that Iinter1 does not satisfy condition (1) of the proof of Proposi-
tion 8.2, nor does the natural implicational condition Icode for Lcode – even
permitting quantification over the number of variables.
We apply Proposition 8.2 to the classes of codes contained in Li to obtain
a uniform characterization of their syntactic monoids. This characterization
is expressed in terms of the following properties of a monoid M .
(M0 ) M is finitely generated.
(M1 ) M \ {1} is a subsemigroup of M .
(M2 ) M has a zero.
(M3 ) M has a disjunctive element c distinct from 1 and 0 such that c = xcy
implies x = y = 1.
(M4 ) M has a disjunctive zero.
(M5 ) There is an element c ∈ annihil(M ) distinct from 0 such that core(M ) =
{c, 0}.
(M6 ) There is an element c distinct from 0 such that

c ∈ core(M ) ∩ annihil(M ).

Theorem 8.1 [54] Let P be an invariant predicate on P such that LP ⊆ Li

where LP is the family of languages L over X such that P is true on (X ∗ , L).
The following conditions on a monoid are equivalent:
(1) M is isomorphic with the syntactic monoid of a (non-empty) code in LP .
(2) M has the properties M0 , M1 , M2 , and M3 and P is true on (M, c).
(3) M has the properties M0 , M1 , M4 , and M5 and P is true on (M, c).
(4) M has the properties M0 , M1 , M4 , and M6 and P is true on (M, c).
62 H. Jürgensen and S. Konstantinidis

Proof: Suppose M is isomorphic with the syntactic monoid of a code L ∈ LP .

As the properties M0 through M6 and P are preserved under isomorphisms
and pointed-monoid isomorphisms, we may assume that M = syn L for some
L ∈ LP . Then L is an infix code. For u ∈ L and x, y ∈ X ∗ , one has xuy ∈ L
if and only if x = y = λ. Thus, L is a single PL -class. Let σL (L) = c. As P
is invariant, P is true on (M, c).
As X is finite, M is finitely generated. Thus M0 holds true.
The empty word forms a PL -class of its own. For, if λ ≡ v(PL ) and u ∈ L
then u ≡ uv(PL ), hence uv ∈ L and, thus, v = λ. This implies M1 .
The residue WL is non-empty as ux ∈ WL for any u ∈ L and x ∈ X. It
also forms an equivalence class, the image of which is the zero of syn L. This
implies M2 .
The element c is distinct from 1 and 0 as λ ∈ / L and WL ∩ L = ∅.
Suppose that c = xcy for some x, y ∈ M . Then there are words u, v ∈ L
and x0 , y 0 ∈ X ∗ such that u = x0 vy 0 , σL (x0 ) = x, and σL (y 0 ) = y, hence
x0 = y 0 = λ, that is, x = y = 1. This proves M3 ; hence (1) implies (2).
Now suppose that (2) obtains. By M3 , c is disjunctive and, therefore,
Wc = {0}. Let N be an ideal of M with N 6= {0} and a ∈ N \ {0}. Then
there are x, y ∈ M such that xay = c. Therefore, c ∈ N and, consequently,
c ∈ core(M ). Moreover, {c, 0} is an ideal, thus core(M ) = {c, 0}. For any
x ∈ M \ {1}, one has xc = 0 = cx as Wc = {0}. This proves M5 .
Now consider a, b ∈ M such that a ≡ b(P0 ). We show that a = b. Then
xay = 0 if and only if xby = 0. If a = 0 then xay = 0 for all x, y; hence,
in particular for x = y = 1, b = 0. Therefore, assume that a 6= 0, b 6= 0,
and a 6= b. Then there are x, y such that xay = c and xby 6= c as c is
disjunctive; moreover, xay ≡ xby(P0 ) as P0 is a congruence. Hence, xby 6= 0
as c 6= 0. Therefore, there are x0 and y 0 such that x0 xbyy 0 = c and x0 6= 1
or y 0 6= 1. As P0 is a congruence, one has x0 xayy 0 ≡ x0 xbyy 0 (P0 ); moreover,
x0 xayy 0 = x0 cy 0 = 0 as c ∈ annihil(M ). Thus, 0 ≡ x0 xbyy 0 (P0 ) = c 6= 0,
a contradiction. Therefore, a = b. This proves M4 ; hence (2) implies (3).
Obviously, (3) implies (4).
Now assume that (4) holds true. We show that this implies (1). As a
first step we prove that core(M ) = {c, 0}. Let a ∈ annihil(M ) ∩ core(M ),
a 6= 0. One has xay = 0 if and only if x 6= 1 or y 6= 1 as a ∈ annihil(M ).
Thus, a ≡ c(P0 ) and, as 0 is disjunctive, a = c. Moreover, {c, 0} is an ideal
and, therefore, core(M ) = {c, 0}. The fact that c ∈ annihil(M ) implies that
xcy = c only if x = 1 = y.
Next, we show that c is disjunctive. Consider a, b ∈ M with a ≡ b(Pc ),
a 6= b. Thus, for all x and y, xay = c if and only if xby = c. As a 6= b and 0 is
disjunctive, there are x, y ∈ M such that, without loss of generality, xay = 0
and xby 6= 0. As core(M ) = {0, c}, c is contained in the ideal M xbyM and,
therefore, there are x0 , y 0 ∈ M such that x0 xbyy 0 = c; on the other hand,
x0 xayy 0 = 0, a contradiction.
 Codes 63

Now consider a finite minimal set X of generators of M and let ϕ be the

monoid morphism of X ∗ onto M which is induced by the inclusion X ⊆ M .
Note that ϕ is non-erasing39 because of M1 . Let L = ϕ−1 (c). Then (X ∗ , L)
is a pointed monoid and M is isomorphic with the syntactic monoid of L via
the isomorphism ψ of syn L onto M given by ψ(σL (x)) = ϕ(x) for x ∈ X ∗ .
ψ is well-defined and ψ(σL (L)) = c. Thus, ϕ is a pointed-monoid morphism
of (X ∗ , L) onto (M, c) and σL is also non-erasing.
Consider u, v ∈ L such that u = xvy for some x, y ∈ X ∗ . Then

ψ(σL (u)) = c = ψ(σL (x))cψ(σL (y)),

hence ψ(σL (x)) = 1 = ψ(σL (y)). As ψ is an isomorphism, one has σL (x) =

λ/PL = σL (y) and x = y = λ as σL is non-erasing. Thus, L is an infix code.
As P is invariant and true on (M, c) it is also true on (X ∗ , L). Therefore,
L ∈ LP . ¤

For the special case of LP = Li , the clause “and P is true on (M, c)” can
be omitted in all statements of Theorem 8.1. In the proof, it is crucial that
X is chosen in such a way that σL is non-erasing as shown by the following
example.

Example 8.2 Consider the monoid M = {1, c, 0} with c2 = 0. By Theo-

rem 8.1, M is isomorphic with the syntactic monoid of an infix code. If we
choose X = {a} and define ϕ : X ∗ → M by

1, if x = λ,
(
ϕ(x) = c, if x = a,
0, otherwise,

then L = ϕ−1 (c) = {a} is an infix code. On the other hand, if X = {a, b}
with ϕ : X ∗ → M given by

1, if x ∈ b∗ ,
(
ϕ(x) = c, if x ∈ b∗ ab∗ ,
0, otherwise,

then L = ϕ−1 (c) = b∗ ab∗ , and this is not an infix code. This shows that it
is important that the morphism ϕ in the proof of Theorem 8.1 be chosen in
such a way that it is non-erasing, and this is guaranteed when X is a minimal
set of generators.

39
X is a minimal set of generators of M as a monoid! The identity element of M
is obtained from the empty word over X.
64 H. Jürgensen and S. Konstantinidis

Theorem 8.1 is applicable, in particular, to Lin and Lin ∩ Lon for n ≥ 1,

to Lpn , Lsn , Lpn ∩Lsn , Lon for n ≥ 2, and to Lh and Lsolid . For the classes Li
and Lh , the statement of Theorem 8.1 is proved in [101]; for a characterization
of the syntactic monoids of hypercodes see also [131] and [135]; for Lpn , Lsn ,
Lin , and Lon with n ≥ 2 similar results are proved in [90], [89], [93], and [132].
By Theorem 6.2 every regular outfix code and every hypercode is finite.
Thus, if L is a regular language in Li ∩ Lo then there is an n ∈ N such that
|w| < n for all w ∈ L. As a consequence, if w ∈ X n X ∗ then w ∈ WL and,
therefore, (syn L \ {1})n = {0}, that is, syn L \ {1} is nilpotent. Recall that
a semigroup with at least two elements is subdirectly irreducible if it has a
unique congruence which differs from the equality and is contained in every
other congruence. By a result of [121], if M is a monoid with zero such that
M \ {1} is a nilpotent subsemigroup of M with a least two elements, then
the zero is disjunctive if and only if M is subdirectly irreducible. This leads
to the following generalization of results due to [131], [135], and [101].
Corollary 8.1 Let P be an invariant predicate on P such that LP ⊆ Li ∩ Lo .
A finite monoid M is isomorphic with the syntactic monoid of a non-empty
regular code in LP if and only if M is subdirectly irreducible, M \ {1} is a
nilpotent subsemigroup of M , and there is an element c, distinct from 0 ∈ M ,
in core(M ) ∩ annihil(M ) such that P is true on (M, c).
Theorem 8.1 and Corollary 8.1 provide characterizations of families of
syntactic monoids for various types of infix codes. Conversely, for a given
class L of infix codes, one can attempt to characterize the family L̂ of all
those languages the syntactic monoid of which is isomorphic with the syn-
tactic monoid of a language in L. For the special case of Lh , a concrete
characterization of L̂h is given in [135]. This establishes a correspondence
between families of languages and families of monoids similar to the one
of [24] between varieties of languages and pseudo-varieties of monoids. In
our context, however, the families of monoids under consideration are usually
not pseudo-varieties, and completing them to pseudo-varieties will introduce
many monoids which correspond to languages of little resemblance to those
under investigation. In essence, the construct of variety is not fine enough
to exhibit the details of the combinatorial structure of codes – let alone of
codes low in the hierarchy.
Theorem 8.2 [47] Let L ⊆ X + , m ∈ syn L with 1 6= m 6= 0, and let
(−1)
L0 = σL (m). The following statements hold true for all n ∈ N:
(1) If L ∈ Lon then L0 ∈ Lon .
(2) If L ∈ Lpn+1 ∪ Lsn+1 then L0 ∈ Lon .
(3) If L ∈ Lh then L0 ∈ Lh .
For n = 1, Theorem 8.2(1) is proved in [50]. For the case of n-infix codes
a weaker version of (2) is proved in [132]. Statement (3) is proved in [101].
 Codes 65

9. Deciding properties of codes

In this section we discuss the following natural question: Given a class L of
codes over X and given a language L ⊆ X + , is it decidable whether L ∈ L?
And if not, under which additional assumptions is this decidable? In view of
the classes of languages introduced in Section 6, we extend this question to
include classes L of languages which are not codes, but are related to codes
in some natural way.
For example, given a language L ⊆ X + in some constructive way,40 one
could ask whether L is 2-code or whether L is a hypercode.
Clearly, in this generality, the question is undecidable. For example, as
shown in Theorem 3.3, if L is the class K ∗ of ∗-codes and L can be any linear
language in X + then it is undecidable in general whether L ∈ L. Thus,
restrictions are needed on the class L and on the types of languages L to be
considered; moreover, these restrictions will depend on each other. For the
classes L, we essentially restrict the consideration to those classes introduced
in Section 6; for the languages L, the restrictions will follow the Chomsky
hierarchy.41 In Table 9.1 we show known decidability results for the classes
of languages in Fig. 7.2 and a few others.42
The proofs of the decidability results shown in Table 9.1 are quite ad
hoc, that is, they rely heavily on the specific properties of the class L at
hand. Given that dependence theory provides a uniform framework for the
definition of most of the natural classes of codes (and related languages), one
can rephrase the decidability problem as follows:
+
Let n ∈ Nℵ0 , let D be an n-dependence system on X + , and let L ⊆ 2X .
For L ∈ L, decide whether L is D-independent.
The challenge of this problem is to find a uniform proof method for decid-
ability results or to find general criteria as to when a given abstract proof
method is applicable. In view of Theorem 3.3, one cannot expect L to be
larger than the class of regular languages in general; on the other hand, also
D will have to satisfy some restrictive conditions, a natural one being that the
set supportn (D) is decidable. Thus it seems appropriate to ask the following
question:

40
The language could be given by a grammar or an acceptor or some other com-
puting device; which type, does not matter as long as the device can be effectively
simulated by one of these.
41
See the general exposition on formal languages in this handbook. Other lan-
guage classes, for example those defined by L systems of various kinds, could be
used. As is quite common in formal language theory, very little is known about the
boundary separating decidable from undecidable cases.
42
This table should be used with some care. Empty entries indicate that either
there is nothing interesting to report or we do not know of an existing or readily
available answer; this does not imply that the answer is not known or is difficult to
find.
66 H. Jürgensen and S. Konstantinidis

Table 9.1. Decidability of code properties.

family decidable for: undecidable for: remarks

η
K L regular, η ≤ ζ L linear, η = ∗ see Theorem 3.2
and Theorem 3.3
Kγ∗ L finite, γ any see Theorem 4.2
SID channel
L2-code L regular, [48]
Ln-code L finite for L regular
and n > 2 the
problem is open
L2-ps , L regular, [49]
L3-ps ,
Lg-3-ps
Lp L regular L linear, emptiness of
Theorem 9.5 L ∩ LX + is
decidable
Ls , Lb L regular L linear analogous to Lp
L4-ps L regular L linear see Theorem 9.5
Lrsema , Lpi , L regular, [50]
Llsema , Lsi
Lo L regular, [50] regular implies
finite
Li L regular, [50] L linear see Theorem 9.5
L pn , L i n , L regular regular implies
L on , L s n finite
for n > 1
Lh , Lu always always finite
Linter L regular, [61] L linear, [61]
Lm-inter , the problem
Lm-intern , seems to be
L1-inter = Q open
Lintern L regular, [125] L linear, [61]
Lsolid L regular, [64] L linear see Theorem 9.5
Lunif-synch , L regular, [73] [78] for finite
Lcircular
Lrdecodable , L regular, [20] [74], [78] for
Lldecodable finite
Lprecirc L regular, [19]
 Codes 67

Let D be an n-dependence system on X + such that, for every set L ∈

Subn X + , it is decidable whether L ∈ D. Given an arbitrary regular
language L over X + , is it decidable whether L ∈ LD ?
Those classes of languages shown in Table 9.1, which can be defined using
dependence systems, and for which a decidability result is known, may seem
to indicate an affirmative answer to this question. However, the general
answer is – not unexpectedly – negative.
Theorem 9.1 [114] There is an n ∈ N and an n-dependence system D on
X + with the following properties:
(a) For every L ∈ Subn X + , it is decidable whether L ∈ D.
(b) It is undecidable whether a given regular language is D-independent.
Proof: Consider an instance (U, V ) of Post’s Correspondence Problem over
the alphabet {0, 1}, where

U = (u0 , u1 , . . . , un−1 ) and V = (v0 , v1 , . . . , vn−1 )

for some n ∈ N and u0 , u1 , . . . , un−1 , v0 , v1 , . . . , vn−1 ∈ {0, 1}∗ . Let X =

{0, 1, c/, $, @} and let DU,V be the smallest 4-dependence system on X ∗ con-
taining all sets of the form

{ūi0 $ūi1 $ · · · $ūik−1 , @v̄j0 $v̄j1 $ · · · $v̄jk−1 , u0 c/v0 $u1 c/v1 $ · · · $un−1 c/vn−1 }

with ūi0 · · · ūik−1 = v̄j0 · · · v̄jk−1 , where k ∈ N and for all l ∈ k there is h ∈ n
such that ūil = uh and v̄jl = vh . For every set L ⊆ X + with |L| < 4, it is
decidable whether L ∈ DU,V .
Consider

LU,V = ({0, 1}∗ $)∗ {0, 1}∗ ∪ @({0, 1}∗ $)∗ {0, 1}∗
∪ {u0 c/v0 $u1 c/v1 $ · · · $un−1 c/vn−1 }.

The language LU,V is regular. Moreover, LU,V is DU,V -dependent if and only
if (U, V ) has a solution. ¤
As a consequence of Theorem 9.1, further restrictions on the n-dependence
systems under consideration are required. We discuss two such approaches,
the former based on results presented in Section 8 above, the latter based on
automaton theoretic considerations.
Theorem 9.2 [54] Let D be a dependence system satisfying the following
conditions:
(1) There is (effectively) an invariant predicate PD on P such that L ∈ LD
if and only if PD is true on (X ∗ , L).
(2) For every L ∈ LD , σL is non-erasing.
Then, for any (constructively given) regular language L ⊆ X + , it is decidable
whether L is D-independent.
68 H. Jürgensen and S. Konstantinidis

This result is an immediate consequence of Proposition 8.1. By Proposi-

tion 8.2, the cases to which Theorem 9.2 is applicable include the following:
Lpn , Lsn , Lb , Lin , Lon for n ≥ 1, Lh , and Lsolid . On the other hand, it is
not applicable to Lcode , and Linter1 , for example.
For Linter we do not know whether Theorem 9.2 applies. Indeed, we do
not even know whether the class is definable by a dependence system.
A totally different approach is proposed in [62]. In contrast to the previous
one, it works only for n-dependence systems with n < ℵ0 . The key idea is,
to express supportn (D) as the set of (n − 1)-tuples accepted by a multi-input
automaton with decidable emptiness problem. We sketch the definitions only
and refer the reader to the references provided for details.
An automaton with abstract storage type T, a T-automaton as defined
in [25] and [27], consists of a finite state control, a set C of storage con-
figurations, an initial configuration c0 ∈ C, and sets T and I of tests and
instructions, respectively. The tests are mappings of C into the set 2, and
the instructions are partial mappings of C into C.
For instance, in the case of pushdown automata the tests of T are used
to check what the topmost stack symbol is and the instructions in I either
pop the stack or push a new symbol onto the stack.
The operation of the automaton consists of reading the input, changing
the internal state, and applying the tests and instructions to the current stor-
age configuration. The current input symbol, the internal state and the result
of the test together non-deterministically determine whether the automaton
reads the next input symbol, changes the internal state, and performs a test
or instruction on the storage configuration. We assume that the automata
accept by final state, that the set of configurations is finitely specified, and
that the sets of tests and instructions are effectively given. All automata
that we consider are non-deterministic and have one-way read-only inputs.
However, we allow them to have more than one input tape.
Let T be an abstract storage type, and let n ∈ N. A T-[n, X]-automaton
is a T-automaton with n one-way input tapes and input alphabet X. Let
A be a T-[n, X]-automaton. An n-tuple (w1 , . . . , wn ) ∈ X + × · · · × X + is
accepted by A if there is a finite sequence of computation steps of A which,
starting at c0 , leads to some final state for w1 , . . . , wn on the input tapes
numbered 1, . . . , n. Let L(A) be the set of n-tuples accepted by A.
Definition 9.1 Let T be an abstract storage type. The emptiness problem for
T is to determine, for a given T-[1, X]-automaton A, whether L(A) = ∅. The
membership problem for T is to determine, for a given T-[1, X]-automaton
A and a word w ∈ X ∗ , whether w ∈ L(A).
For an abstract storage type, the membership problem is decidable if and
only if the emptiness problem is decidable [62]. This equivalence holds true
for the definition of abstract storage types as sketched above which is due to
[27] and [25], but does not hold true for a more general definition of abstract
storage types proposed in [26] and [28].
 Codes 69

The abstract storage types to be considered are built from pushdowns

and stacks. The main difference between a pushdown and a stack is that, on
a pushdown, only the symbol at the top is accessible while, on a stack the
symbols below the top are also accessible, but in read-only mode. Pushdown
[1, X]-automata accept the context-free languages, and the emptiness prob-
lem is decidable for context-free languages, hence, for the abstract storage
type of pushdown. A k-iterated pushdown, for k ∈ N, is an abstract storage
type in which the storage configurations consist of pushdown configurations
in the case of k = 1 and of a pushdown of (k − 1)-iterated pushdown con-
figurations in the case of k > 1. In a similar fashion one defines k-iterated
stacks. A characterization of the languages accepted by k-iterated pushdown
[1, X]-automata is given in [17] where it is also shown that the emptiness
problem for these languages is decidable. In [25] it is shown that a k-iterated
stack can be simulated by a 2k-iterated pushdown. Therefore, the emptiness
problem is also decidable for k-iterated stacks.
A counter is a pushdown the tape alphabet of which is a singleton set.
A counter is said to have a reversal bound of n ∈ N0 if, in any computation,
the counter may switch between pushing and popping at most n times. A
reversal-bounded multi-counter consists of k counters, for some k ∈ N, which
have a reversal bound of n for some n ∈ N0 . Emptiness is decidable for the
languages accepted by reversal-bounded multi-counter [1, X]-automata; this
remains true even when the input tape is two-way reversal-bounded or when
the automaton has an additional pushdown, but not both [46].

Theorem 9.3 [62] Let T be an abstract storage type with decidable emptiness
problem. Then, for any T-[n, X]-automaton A and any regular languages
L1 , . . . , Ln over X, it is decidable whether L(A) ∩ L1 × · · · × Ln is empty.

Now we establish the connection to language classes defined by (n + 1)-

dependence systems with n < ℵ0 . For such a dependence system D, consider
a set ωD of n-tuples satisfying the following two conditions:43
S
• If (w0 , . . . , wn−1 ) ∈ ωD then i∈n {wi } ∈ D.
• If w0 , . . . , wk−1 are k distinct words such that {w0 , . . . , wk−1 } ∈ D and
k ≤ n then (wπ(0) , . . . , wπ(n−1) ) ∈ ωD for some mapping π of n onto k.
Thus, a set L ⊆ X + is D-independent if and only if ωD ∩ L × · · · × L = ∅.
Applying Theorem 9.3, one obtains the following general decidability result.

Theorem 9.4 [62] Let D be an (n+1)-dependence system on X + with n < ℵ0

and let T be an abstract storage type with decidable emptiness problem such
that there is a T-[n, X]-automaton A with L(A) = ωD . Then, for any regular
language L over X, it is decidable whether L ∈ LD .

43
The details concerning the connection between n-ary relations and (n + 1)-de-
pendence systems are explained in [66], but are not essential in the present context.
70 H. Jürgensen and S. Konstantinidis

Table 9.2. Language classes and abstract storage types proving decidability.

families abstract storage type

L3-ps , L4-ps , Lpn , Lin , Lon , Lsn , Lb , Lh , Lu , finite state
Lsolid , Lintern
L2-ps , Lg-3-ps , L2-code stack

To apply Theorem 9.4 to a given (n + 1)-dependence system D one has

to exhibit an appropriate n-ary relation ωD and an abstract storage type T
with decidable emptiness problem such that ωD is accepted by a T-[n, X]-
automaton. We list language classes and abstract storage types establishing
the decidability in Table 9.2. Note that non-determinism is used heavily in
several of these cases.
The decision method of Theorem 9.4 extends far beyond the hierarchy of
codes. The following example is discussed briefly in [62].
Example 9.1 With every word w ∈ X ∗ one associates a mapping πw of X
into N0 such that πw (x), for x ∈ X, is the number of occurrences of x in w;
with a slightly different notation, πw is usually called the Parikh vector of w.
Consider the dependence system DParikh such that L ∈ DParikh if there are
words w, v ∈ L with w 6= v and πw = πv . To decide DParikh -dependence, one
uses a [2, X]-automaton with |X| + 1 counters with a reversal bound of 1 for
each counter.
The two general decision methods presented differ in two respects: By its
very nature, the automaton-based approach44 cannot handle n-dependence
when the only known bound on n is ℵ0 , as this approach uses automata with
n − 1 input tapes; thus, it is not applicable to the class Lcode of codes –
more precisely, to the relation or dependence system defining this class. On
the other hand, the monoid-based approach seems not to be suitable when
syntactic morphisms may be erasing or for classes the definition of which
requires the quantification over the number of variables. Neither method
seems to be able to deal with the case of intercodes. This is not surprising
because, as mentioned before, it is not very likely that the class of intercodes
can be defined by a dependence system.
The decidability of Linter is proved in [61] and [105] using completely
different methods. Neither of these approaches seems to be related to the
two proof methods discussed in this handbook chapter.
The monoid-based and automaton-based proof methods are general and
can be applied to many cases; they are, however, not equivalent. Whether
a universal proof method – or at least a more comprehensive one – exists,
continues to be an intriguing open problem.

44
A different transducer-based technique is used in [43] to decide other code-
related problems.
 Codes 71

We conclude this section with a theorem asserting the undecidability of

several properties for linear languages as shown in Table 9.1.
Theorem 9.5 There is no algorithm which, given a linear grammar G, al-
ways decides whether the language generated by G is a prefix code, a suffix
code, a bifix code, a 4-ps-code, an infix code, or a solid code.
Sketch of the proof: The proof is analogous to that of Theorem 3.3. Hence we
only sketch the major steps and refer to the proof of Theorem 3.3 for details
and unexplained notation. Let (U, V ) be an instance of Post’s Correspon-
dence Problem, where

U = (u0 , u1 , . . . , un−1 ) and V = (v0 , v1 , . . . , vn−1 ).

For Lp , consider the linear language L consisting of precisely the words

of the form

β(im−1 )/cβ(im−2 )/c · · · β(i0 )$ui0 · · · uim−2 uim−1 #

and
β(im−1 )/cβ(im−2 )/c · · · β(i0 )$vi0 · · · vim−2 vim−1 ##.

Then (U, V ) has a solution if and only if L ∩ L# 6= ∅. Moreover, L ∩ L#

is empty if and only if L is a prefix code. Thus, for linear languages it is
undecidable in general whether they are prefix codes. By duality, also the
property of being a suffix code is undecidable for linear languages.
For L4-ps = Lp ∪ Ls and Lb , consider the linear language L consisting of
precisely the words of the form

#β(im−1 )/cβ(im−2 )/c · · · β(i0 )$ui0 · · · uim−2 uim−1 #,

#β(im−1 )/cβ(im−2 )/c · · · β(i0 )$vi0 · · · vim−2 vim−1 ##,
and
##β(im−1 )/cβ(im−2 )/c · · · β(i0 )$vi0 · · · vim−2 vim−1 #.

If (U, V ) has a solution then L ∩ L# 6= ∅ and L ∩ #L 6= ∅. Moreover, L ∩ L#

is empty if and only if L is a prefix code; L ∩ #L is empty if and only if L is
a suffix code. Thus, if (U, V ) has a solution then L ∈/ Lp ∪ Ls = L4-ps , hence
L∈ / Lb . On the other hand, if (U, V ) has no solution then L ∈ Lp ∩ Ls = Lb ,
hence L ∈ L4-ps . This proves the undecidability for L4-ps and Lb .
For Li , consider the linear language L consisting of precisely the words of
the form

#β(im−1 )/cβ(im−2 )/c · · · β(i0 )$ui0 · · · uim−2 uim−1 #

and
##β(im−1 )/cβ(im−2 )/c · · · β(i0 )$vi0 · · · vim−2 vim−1 ##.
72 H. Jürgensen and S. Konstantinidis

Then (U, V ) has a solution if and only if L is not an infix code.

For Lsolid , we add a new symbol % to the alphabet. Now consider the
linear language L consisting of precisely the words of the form

#β(im−1 )/cβ(im−2 )/c · · · β(i0 )$ui0 · · · uim−2 uim−1 %

and
##β(im−1 )/cβ(im−2 )/c · · · β(i0 )$vi0 · · · vim−2 vim−1 %%.

Then (U, V ) has a solution if and only if L is not a solid code. ¤

10. Maximal codes

Let L be a family of languages over the alphabet X. A language L over X
is said to be L-maximal if L ∈ L and, for L0 ∈ L, L ⊆ L0 implies L = L0 . A
language L over X is said to be dense if X ∗ wX ∗ ∩ L 6= ∅ for every w ∈ X ∗ .
A language which is not dense is called thin. A language L is complete if and
only if L∗ is dense. A language L over X is right dense if wX ∗ ∩ L 6= ∅ for
every w ∈ X ∗ .
Maximality and completeness concern the economy of a code. If L is a
complete code then every word occurs as part of a message, hence no part of
X ∗ is “wasted.” If L is a class of codes, and L is L-maximal, then L provides
for the encoding of |L| distinct symbols and L cannot be “improved” given
the constraints imposed by the properties of L. Other important criteria
concerning the economy of a code include the average word length (see [4]).
We turn our attention to the following two issues: For a given family
L in the hierarchy of codes, one seeks a characterization of the L-maximal,
the finite L-maximal, and the regular L-maximal languages. For a given
L ∈ L, can L be embedded in a L-maximal, a finite L-maximal, or a regular
L-maximal language?
For most of natural classes L of codes, the characterization of the L-
maximal codes is an open problem. Significant results are known for the
classes Lcode of codes, Lp of prefix codes, Ls of suffix codes, Lb of bifix codes
(see [4]), and for certain classes which are quite low in the hierarchy. We
quote a few classical results from [4]. For a recent survey see [8].
Theorem 10.1 [4] Let X be an alphabet with |X| > 1, and let L ⊆ X + . The
following statements hold true:
(a) If L is Lcode -maximal then L is complete.
(b) If L is thin and complete then L is Lcode -maximal.
(c) If L is thin then the following statements are equivalent:
(c1) L is Lp -maximal;
(c2) L ∈ Lp and L is Lcode -maximal.
(d) If L is thin then the following statements are equivalent:
(d1) L is Lb -maximal;
(d2) L ∈ Lb and L is Lcode –maximal;
 Codes 73

(d3) L is Lp -maximal and Ls -maximal.

(e) If L is thin then the following statements are equivalent:
(e1) L is Lcircular -maximal;
(e2) L ∈ Lcircular and L is Lcode -maximal.
(f ) If L is thin then the following statements are equivalent:
(f1) L is Lrdecodable -maximal;
(f2) L ∈ Lrdecodable and L is Lcode -maximal.
The class of thin codes is quite large as it contains the class of all regular
codes. The proof of this statement given in [4] implies the following stronger
result.
Theorem 10.2 Let X be an alphabet with |X| > 1 and let L be a family of
languages over X such that every L ∈ L is the subset of a cross section of
∼√ . Then every regular language in L is thin.
By [18] and [48], the 2-codes are precisely the subsets of cross sections of
the equivalence relation ∼√ .
Corollary 10.1 Every regular language in L2-code is thin.
The statements (c)–(f) of Theorem 10.1 show an interesting pattern, that
has been observed in several additional cases. Consider two classes L and L 0
of languages such that L ⊆ L0 . The pattern is as follows:
Suppose L satisfies a certain condition C; then L is L-maximal if and
only if L ∈ L and L is L0 -maximal.
In Theorem 10.1 the condition C is that L be thin. One part of this type of
statement follows, regardless of C, from the following general observation.
Lemma 10.1 Let L and L0 be families of sets such that L ⊆ L0 and let
L ∈ L. If L is L0 -maximal then L is L-maximal
The converse Lemma 10.1 usually requires the special condition C. We
list a few similar results.
Theorem 10.3 Let X be an alphabet with |X| > 1 and let L ⊆ X + . The
following statements hold true:
(a) Suppose L is a left (right) dense prefix (suffix) code. Then L is L3-ps -
maximal if and only if L is Lp -maximal (Ls -maximal) [49].
(b) Suppose L is a Lp -maximal (Ls -maximal) suffix (prefix) code. Then L is
Ls -maximal (Lp -maximal) if and only if L is L3-ps -maximal [49].
(c) No 3-ps-code is a maximal 2-ps-code [49].
(d) No 2-ps-code is a maximal 2-code; every maximal 2-ps-code is dense [49].
(e) If L is a maximal prefix code and a maximal suffix code then L is a maximal
3-ps-code [49].
(f ) No g-3-ps-code is a maximal 2-ps-code; there are finite maximal g-3-ps-
codes and also finite maximal 3-ps-codes which are not maximal g-3-ps-
codes [49].
 74 H. Jürgensen and S. Konstantinidis

(g) A language is Lpi -maximal (Lsi -maximal) if and only if it is a p-infix

(s-infix) code which is Lp -maximal (Ls -maximal) [50].
(h) Every non-empty right (left) semaphore code is Lp -maximal (Ls -maximal)
[4], hence Lrsema -maximal (Llsema -maximal).
(i) A language is Lpi -maximal (Lsi -maximal) if and only if it is a non-empty
right (left) semaphore code [50].
(j) An Lb -maximal language is Lp -maximal or Ls -maximal.
(k) An Lb -maximal infix code is in Lrsema ∩ Lsi or Llsema ∩ Lpi [50].
(l) An infix code which is Lp -maximal or Ls -maximal is a uniform code which
is Lu -maximal, hence is of the form X n for some n ∈ N [50].
(m) An outfix code which is Lp -maximal or Ls -maximal is Lu -maximal [50].
(n) An infix code or outfix code is Lcode -maximal if and only if it is Lp -
maximal and this holds if and only if it is Lu -maximal [90], [89].
(o) A p-infix (s-infix) code is Ls -maximal (Lp -maximal) if and only if it is
Lu -maximal [92].

Note that Theorem 10.3(c)–(d) are used in [49] to show that L3-ps (
L2-ps ( L2-code .
Numerous results characterizing L-maximal sets of a given family L exist
in the literature (usually satisfying certain additional conditions). Several of
these can be found in [6], [146], [120], [118] for Lp and Ls , [142], [30], [29],
[23], [109] for Lcode , [7] for Lrdecodable , [124] for Lh , and [51] for L2-code .
The basic question raised, but not solved by these results is as follows:
Given two dependence systems D and D 0 on X + such that LD ⊆ LD0 ,
under which condition C on L and depending on D and D 0 is it true
that L being LD -maximal implies that L is also LD0 -maximal?
Taking into account that LD ⊆ LD0 if and only if D 0 ⊆ D, one can consider
the following variant of this question:
Given a condition C, for any dependence system D what are the mini-
mal dependence systems D 0 with D 0 ⊆ D such that L being LD -maximal
implies that L is LD0 -maximal?
Similarly, one could start with D 0 and ask for a characterization of maximal
dependence systems D with the corresponding properties. From the applica-
tion point of view, any condition C that excludes no regular languages – or
at least no finite languages – would still be of interest.
We now turn to the second issue: Let L be a family of languages and
L ∈ L; can L be embedded in an L-maximal, a finite L-maximal, or a regular
L-maximal language? The following rather general result implies that the
first problem, that of embedding L in an L-maximal language can always be
achieved when L is the family of D-independent sets for some dependence
system D.

Theorem 10.4 [56] Let D be a dependence system on a set S. Every D-in-

dependent set can be embedded in a maximal D-independent set.
 Codes 75

Proof: We use Zorn’s lemma. Consider an ascending chain {Li | i ∈ I} of

D-independent subsets, where I is anS arbitrary, totally ordered index set and
Li ⊆ Lj for i ≤ j, i, j ∈ I. Let L = i∈I Li . Suppose that L is D-dependent.
Then there is a finite, non-empty subset L0 of L such that L0 ∈ D. Hence,
L0 ⊆ Li for some i ∈ I, and Li is D-dependent, a contradiction. ¤

From Theorem 10.4 it follows that every code over X is contained in a

maximal code over X (see [4], p. 41), every prefix code is contained in a
maximal prefix code, etc. Indeed, the proof of Theorem 10.4 captures the
abstract pattern of all proofs of such results in the theory of codes.
We now turn to the second and third parts of our question: Suppose
L ∈ L is finite or regular; can L be embedded in a finite or regular L-maximal
language? The answer is only known in few cases.
For the class Lcode , an example of [108] shows that there are finite codes
which cannot be embedded in finite maximal codes. The smallest known
example has 4 elements. On the other hand, every 2-element code can be
embedded in a finite maximal code [109]. By [23], every regular code can
be embedded in a regular maximal code. Every finite prefix code can be
embedded in a finite maximal prefix code [109]. Every regular or thin code
with decoding delay45 d can be embedded in a maximal code with decoding
delay d which is also regular or thin, respectively, [7], [9]. In [55], we hope
to have established that every finite solid code can be embedded in a finite
maximal solid code.
The abundance of results concerning maximality, completeness, dense-
ness, and related properties available about many special classes of codes
made it impossible to include or even just mention every single one. Our
aim, in this section, was to exhibit the structure of typical problems in this
field and to show typical examples of results. It would be a very interesting
and probably very ambitious project to attempt a unified approach to this
whole field along the lines of thought suggested.

11. Solid codes

In this section we examine the class of Lsolid in some detail. Solid codes have
some remarkable synchronization properties in the presence of SID-channel
errors.
Let η ≤ ζ. For any word schema w ∈ S(X η ) and any language K ⊆ X + ,
an error decomposition of w over K is a factorization

w = · · · (u1 )(w1 )(u2 )(w2 ) · · ·

with the following properties:

(1) wi ∈ S(K) for all i.

45
For the noiseless channel, ∗-words, and right decoding.
76 H. Jürgensen and S. Konstantinidis

(2) ui ∈ S(X ≤η ) for all i.

(3) For all i, no word schema v ∈ S(K) is an infix of ui .
Thus, an error decomposition of a word schema w over K consists of factors
belonging to K and factors which do not contain code words as infixes. For
example, if K is the uniform code {010, 001}, then the word schema 0010010
has the two error decompositions (0)(010)(010) and (001)(001)(0) over K.
Theorem 11.1 [64] K ⊆ X + is a solid code if and only if every word schema
w ∈ S(X ∗ ) has a unique error decomposition 46 over K.
Suppose a solid code K is used for information transmission using an SID-
channel γ and that w 0 is a γ-received η-message over K. Then w 0 has a unique
error decomposition over K; thus any code word of the original message that
was transmitted correctly will also be identified correctly through the error
decomposition of w 0 over K. If γ and K are such that it is highly unlikely
that a code word will result from the errors in γ acting on messages over
K then, with high probability, all code words detected in w 0 were in the
original message, and in the same order. Any received correctly transmitted
code word will restore the synchronization completely. K may not be (γ, η)-
correcting, but, if errors have a reasonably low probability and messages
contain sufficient redundancy, they can be sufficient to achieve nearly error-
free information transmission. In general, the actual quality of the solid code
will, of course, depend on how well it matches the channel.
Theorem 11.2 Let η ≤ ζ and let K be a solid code. Every η-word schema
over X has a unique error decomposition over K up to equivalence.
Proof: Let K be a solid code and K 0 = X ∗ \ X ∗ KX ∗ . Let w be an η-word
schema over X, and let ϕ and ψ be factorizations of w over S(K ∪ K 0 ) such
that
S(K 0 ), if i is even,
½
ϕ(i), ψ(i) ∈
S(K), if i is odd,
for i ∈ η; for the purposes of this proof, a factorization having this last
property is said to be alternating. We have to show that ϕ ∼ ψ.
First, we consider the case of η = ω. In this case, ϕ ∼ ψ if and only
if ϕ = ψ. Suppose, ϕ 6= ψ, and let i ∈ ω be minimal with ϕ(i) 6= ψ(i).
Then, without loss of generality, |ψ(i)| < |ϕ(i)| and ψ(i) is a prefix of ϕ(i).
Let x be the non-empty word schema such that ϕ(i) = ψ(i)x. As K is a
solid code, i cannot be odd. Thus, i is even and ψ(i), ϕ(i) ∈ S(K 0 ). Hence,
ϕ(i + 1), ψ(i + 1) ∈ S(K). If |ψ(i + 1)| ≤ |x| then ψ(i + 1) is an infix of

46
Using the property of unique error decompositions, solid codes seem to have
been introduced first in [126]. The definition used in this handbook chapter was
derived as a characterization in [64]. With our present definition, solid codes were
introduced already much earlier in [77] as strongly regular codes and re-named in [84]
into codes without overlaps.
 Codes 77

ϕ(i) ∈ S(K 0 ), contradicting the definition of K 0 . Therefore, |ψ(i + 1)| > |x|.
But then ϕ(i + 1) is an infix of ψ(i + 1) or a proper prefix of ϕ(i + 1) is equal
to a proper suffix of ψ(i + 1), contradicting the assumption that K is a solid
code. This proves ϕ = ψ. The case of η = −ω is settled by duality.
Now, let η = ζ. We distinguish two cases.
Suppose there exists l ∈ ζ such that, with respect to both ϕ and ψ, a
factor starts at position l in w. Let these be the factors with numbers i
and j respectively. If ϕ(i) = λ then i is even and ϕ(i + 1) ∈ S(K), hence
ϕ(i + 1) 6= λ; in this case we use i + 1 instead of i, and similarly for ψ and
j. Hence, without loss of generality, we assume that ϕ(i) and ψ(j) are both
non-empty. For n ∈ ω, let

λ, if n=0 and ϕ(i) ∈ S(K),


ϕ(i) ∈ S(K 0 ),

ϕ(i), if n=0 and

ϕ1 (n) =
 ϕ(i + n − 1),
 if n>0 and ϕ(i) ∈ S(K),
ϕ(i + n), if n>0 and ϕ(i) ∈ S(K 0 ),

λ, if n=0 and ψ(j) ∈ S(K),


ψ(j) ∈ S(K 0 ),

ψ(j), if n=0 and

ψ1 (n) =
 ψ(j + n − 1), if n>0 and ψ(j) ∈ S(K),
ψ(j) ∈ S(K 0 ),

ψ(j + n), if n>0 and
and
w1 (n) = w(n + l).
Then ϕ1 and ψ1 are alternating factorizations of w1 over S(K ∪ K 0 ) and,
therefore, ϕ1 = ψ1 . Similarly, one obtains alternating factorizations ϕ2 and
ψ2 of w2 , given by
w2 (n) = w(l + n − 1)
for n ∈ −ω, over S(K ∪ K 0 ) and, again, ϕ2 = ψ2 . For n ∈ ζ, let
 
 ϕ2 (0)ϕ1 (0),  ψ2 (0)ψ1 (0), if n = 0,
ϕ0 (n) = ϕ1 (n), and ψ 0 (n) = ψ1 (n), if n > 0,
ϕ2 (n), ψ2 (n), if n < 0,
 

and let w 0 = w2 w1 . Then ϕ0 and ψ 0 are alternating factorizations of w 0 over

S(K ∪ K 0 ). Moreover, ϕ0 = ψ 0 and ϕ ∼ ψ.
Finally, suppose there is no l ∈ ζ such that, with respect to both ϕ and
ψ, a factor starts at position l in w. Observe that ϕ(1) ∈ S(K). Then there
is a j ∈ ζ such that ψ(j) is an infix of a proper suffix of ϕ(1) or a proper
prefix of ψ(j) is a proper suffix of ϕ(1), and ψ(j − 1) is an infix of a proper
prefix of ϕ(1) or a proper suffix of ψ(j − 1) is a proper prefix of ϕ(1). One of
the two word schemata, ψ(j) and ψ(j − 1), is in S(K). As K is a solid code,
we obtain a contradiction. ¤
78 H. Jürgensen and S. Konstantinidis

Corollary 11.1 Every solid code is a ζ-code.

Proof: Let w be a ζ-message over K. By Theorem 11.2, w has a unique error
decomposition over K. As w is a ζ-message over K, the error decomposition
is a factorization over K. Thus K is uniquely ζ-decodable. ¤
For finite right decodable codes, the decoding process can be performed
by a finite transducer. Let X and Y be alphabets, with |X| > 1 and |Y | > 1.
Let K be a right decodable η-code over Y with |K| = |X|. Let f be an
arbitrary bijection of X onto K. Let ϑ ≤ η and ϑ < ζ. As in Section 5,
let Ff be the encoding determined by f . Given these assumptions, Ff is a
mapping of X ¨ into Y ¨ and its restriction to X ϑ is an injective mapping of
X ϑ into Y ϑ . In the absence of noise, the restriction Gϑf of Ff−1 to K ϑ is a
ϑ-decoding for f . We may assume that η ≤ ω, hence ϑ ≤ ω. Consider a
ϑ-message w over K. Let v = S(Gϑf (w)). Then v is the unique ϑ-word over
X such that (v, w) ∈ Ff . Let ϕ be the factorization of w over K. Then
v(i) = f −1 (ϕ(i)) for all i ∈ ϑ. As K is right decodable, with delay d say,
and finite, the decoding Gϑf of Ff can be computed by a finite automaton
which needs to be able to store no more than d + 1 code words at any given
moment. Such an automaton will output λ during a state transition if the
information seen and stored so far is insufficient to determine the next symbol
of the decoding; it will output the next symbol when the information suffices.
An automaton computing Gϑf is a special kind of deterministic transducer,
a ϑ-decoder for f . Such ϑ-decoders, called also decoding automata, have
been studied in many contexts. For the purposes of the present section on
solid codes, we refer to [75], [76], [78], [77], [33], and [111]. Some classes of
finite right decodable codes can be characterized by the type of transducers
required for their decoding. We present such a characterization for finite solid
codes [111].
Recall that a (finite) deterministic ϑ-transducer is a construct
A = (Y, X, Q, δ, µ)
with the following properties and interpretation:
(1) Y is the input alphabet and X is the output alphabet of A.
(2) Q is a finite non-empty set, the set of states (state symbols) of A.
(3) δ is a mapping of Q × Y into Q, the transition function of A.
(4) µ is a mapping of Q × Y into X ∗ , the output function of A.
One extends the transition and output functions to input ϑ-words over Y by
½
q, if w = λ,
δ(q, w) =
δ(δ(q, w0 ), w1 w2 · · ·), otherwise,
and ½
λ, if w = λ,
µ(q, w) =
µ(q, w0 )µ(δ(q, w0 ), w1 w2 · · ·), otherwise,
for q ∈ Q and w = w0 w1 w2 · · · ∈ Y ≤ϑ and w0 , w1 , w2 , . . . ∈ Y .
 Codes 79

Definition 11.1 Let ϑ ≤ ω and let X and Y be alphabets with |X| > 1
and |Y | > 1. Let K ⊆ Y + such that |K| = |X| and let f be a bijection of
X onto K. A state-invariant decoder for f without look-ahead is a finite
deterministic ϑ-transducer A = (Y, X, Q, δ, µ) with the following properties:
(1) For all v ∈ K and all q ∈ Q, µ(q, v) = f −1 (v).
(2) For all v ∈ K, all proper prefixes u of v, and for all q ∈ Q, µ(q, u) = λ.

Theorem 11.3 [111] Let ϑ ≤ ω, let X and Y be alphabets with |X| > 1 and
|Y | > 1, let K ⊆ Y + such that |K| = |X| and let f be a bijection of X onto
K. Then K is a solid code if and only if there is a state-invariant decoder
for f without look-ahead.
Proof: Let K and f be given and let A = (Y, X, Q, δ, µ) be a state-invariant
decoder for f without look-ahead. Suppose that K is not a solid code. We
distinguish two cases.
Case 1: There are u, v ∈ K such that u is a proper infix of v. In this case,
v = v1 uv2 for some words v1 and v2 with at least one of v1 and v2 non-empty.
For any q ∈ Q, one has µ(q, v1 ) = λ. Let q 0 = δ(q, v1 ). If v2 6= λ then v1 u is
a proper prefix of v and, by this, µ(q, v1 u) = λ; on the other hand,

µ(q, v1 u) = λµ(q 0 , u) = f −1 (u) 6= λ,

a contradiction. Finally, if v2 = λ, then

µ(q, v) = f −1 (v) 6= f −1 (u) = µ(q, v1 u),

again a contradiction. This proves that K is an infix code.

Case 2: There are u, v ∈ K such that a proper prefix of u is a proper
suffix of v. In this case, u = wu1 and v = v1 w for some non-empty words u1 ,
v1 , and w. For any state q ∈ Q, one has

µ(q, v) = µ(q, v1 w) = λµ(q 0 , w) = f −1 (v)

where q 0 = δ(q, v1 ), hence µ(q 0 , w) = f −1 (v). On the other hand, µ(q 0 , w) =

λ, as w is a proper prefix of u. This contradiction implies that K is overlap-
free.
To prove the converse, we assume that K is a solid code with |K| =
|X| and that f is a bijection of X onto K. We define a transducer A =
(Y, X, Q, δ, µ) as follows. Let Q = Pref(K) ∪ {λ}. For any w ∈ X ∗ , let σ(w)
be the longest suffix of w which is in Q ∪ K. Then
½
σ(qy), if σ(qy) ∈ / K,
δ(q, y) =
λ, otherwise,
and ½
λ, if σ(qy) ∈
/ K,
µ(q, y) =
f −1 (qy), if σ(qy) ∈ K,
80 H. Jürgensen and S. Konstantinidis

for all q ∈ Q and y ∈ Y .

One verifies that, for q ∈ Q and w ∈ Y ∗ ,
½
σ(qw), if σ(qw) ∈/ K,
δ(q, w) =
λ, if σ(qw) ∈ K.

Moreover, as K is a solid code, if a suffix of qw is in K then no other suffix

of qw is in K. Therefore µ is well-defined and µ(q, w) = f −1 (w) for w ∈ K.
If v is a proper prefix of a word w ∈ K then σ(qv) ∈ / K as K is a solid code.
Hence µ(q, v) = λ. Thus, A has the required properties. ¤
The two properties defining solid codes, to be an infix code and to be
overlap-free, impose severe restrictions on the selection of code words. One
has to expect that only very few words of any given length can be used in
a solid code and that, as a consequence, the average code word length and
the redundancy of a solid code will be very large. The next two theorems
examine these issues.
Recall that, for functions
¡ f,¢g : N → R+ , one writes f . g (or f (n) .
g(n)) if lim supn→∞ f (n)/g(n) ≤ 1; one writes f & g (or f (n) & g(n)) if
¡ ¢
lim inf n→∞ f (n)/g(n) ≥ 1; one writes f ∼ g (or f (n) ∼ g(n)) if f . g and
¡ ¢
g . f . Note that f ∼ g if and only if limn→∞ f (n)/g(n) exists and is equal
to 1.
Theorem 11.4 [77], [84] For n ∈ N and |X| = r > 1, let µsolid (n) be the
maximal number of code words of a solid code in X n . Then
¶n−1 n
rn ln r
µ
1 r
1− ≥ µsolid (n) & r/(r−1) .
n n nr

Consider an injective mapping κ of N0 into X ∗ such that |κ(i)| ≤ |κ(i + 1)|

for all i ∈ N0 , and let Kκ = κ(N0 ). We refer to such a mapping κ as an
injective, length-monotonic mapping. Let %κ be the mapping of N into N
given by
%κ (i) = |κ(i)| − blogr ic − 1
for i ∈ N. Intuitively, if Kκ is considered as a code to encode the non-negative
integers, that is, encode i by κ(i), then %κ measures how many more digits are
needed by this encoding than by the usual positional number representation
at base r (which is optimal). For this reason, %κ is sometimes referred to as
the redundancy of κ or of Kκ .
Theorem 11.5 Let |X| = r > 1. The following statements hold true:
(1) There exists an injective length-monotonic mapping κ : N0 → X ∗ such
that Kκ is a prefix code and %κ (n) ∼ logr logr n as n → ∞ [82].
(2) For r = 2, there exists an injective length-monotonic mapping κ : N 0 →
X ∗ such that Kκ ∈ Lp ∩ Lol-free and %κ (n) . 32 log2 log2 n as n → ∞
[95], [84].
 Codes 81

(3) For any injective length-monotonic mapping κ : N0 → X ∗ such that

Kκ ∈ Lsolid one has %κ (n) ≥ c1 logr n + c2 for some constants c1 and c2
with c1 > 0 [84].
The construction of [95] used in [84] for Theorem 11.5(2) is of considerable
interest in its own right.47 Let X = {0, 1}. For i ∈ N0 and n ∈ N, we define
the language

 {0}, if i = 0,

S
Ki,n = 1K(j1 , n) · · · K(jn , n), if i > 0.
 j1 ,j2 ,...,jn ∈N0
j1 +j2 +···+jn =i−1

Let [
K(n) = K(i, n).
i∈N0

Then K(n) is a prefix code; every word in K(i, n) has length ni + 1 and
contains i occurrences of the symbol 1; every word is a prefix of some word
in K(n); moreover, µ ¶
1 ni + 1
|K(i, n)| = .
ni + 1 i
Now consider an injective length-monotonic mapping κ : N0 → X ∗ such that
Kκ = K(2). One computes that

%κ (i)
lim ≤1
i→∞ 3 log2 log2 i
2

as required.
Interpreting %κ as redundancy, Theorem 11.5 shows that solid codes have
a greater redundancy than prefix codes, log n compared to log log n, and that
this difference is, essentially, not due to the overlap-freeness, but to the fact
that they are infix codes. Thus, the penalty in redundancy is not really paid
for the synchronization capabilities – even in the presence of noise –, but for
the ability of infix codes to detect certain kinds of insertion or deletion errors.
For the remainder of this section, we focus on combinatorial properties of
solid codes and their relation to other types of codes.
Theorem 11.6 [64] The class of solid codes is closed under inverse non-
erasing morphisms. Moreover, if X and Y are alphabets and ϕ is a non-
erasing morphism of X ∗ into Y ∗ , then ϕ maps solid codes onto solid codes
if and only if the restriction of ϕ to X is injective and, for any a, b ∈ X, the
set {h(a), h(b)} is a solid code.

47
It is used in [95] to exhibit the relation among four different “completeness”
conditions for prefix codes which are known to be equivalent for finite prefix codes,
but turn out not to be equivalent for infinite prefix codes.
82 H. Jürgensen and S. Konstantinidis

Theorem 11.7 [126] Lsolid is a proper subset of Linter1 , hence a proper subset
of Li and Q.

Let N = (N0 , N1 , . . .) be a sequence such that, for k ∈ N0 , Nk is a set

of 2k-tuples of positive integers. Let f = (f0 , f1 , . . .) and g = (g0 , g1 , . . .) be
sequences of mappings, such that, for k ∈ N0 , fk and gk map Nk into N. We
say that f and g satisfy the solidity condition if, for all k ∈ N0 , all x, y ∈ Nk
where x = (x1 , . . . , x2k ) and y = (y1 , . . . , y2k ), and t with 1 ≤ t ≤ k, one has

0∗ 0fk (x) 1x1 0x2 · · · 1x2t−1 ∩ 0y2(k−t+1) 1y2(k−t+1)+1 · · · 1y2k−1 0y2k 1gk (y) 1∗ = ∅.

We denote the fact that f and g satisfy the solidity condition for N by
Sol(N, f, g).

Lemma 11.1 [55] Let X = {0, 1}, let C ⊆ 0+ X ∗ 1+ be a solid code, and for
k ∈ N0 let

Nk = {(j1 , i1 , j2 , i2 , . . . , jk , ik ) | C ∩ 0+ 1j1 0i1 1j2 0i2 · · · 1jk 0ik 1+ 6= ∅}.

There are sequences f = (f0 , f1 , . . .) and g = (g0 , g1 , . . .) with the following

properties:
(1) For all k ∈ N0 , fk and gk are mappings of Nk into N.
(2) Sol(N, f, g) obtains.
(3) For all k ∈ N0 and all x ∈ Nk , one has

C ∩ 0+ 1x1 0x2 · · · 1x2k−1 0x2k 1+ = {0fk (x) 1x1 0x2 · · · 1x2k−1 0x2k 1gk (x) }.

Conversely, let N = (N0 , N1 , . . .) be a sequence such that, for k ∈ N0 , Nk

is a set of 2k-tuples of positive integers. Let f and g be sequences of map-
pings satisfying (1) and (2). Then, for any k ∈ N with Nk 6= ∅, the set
{0fk (x) 1x1 0x2 · · · 1x2k−1 0x2k 1gk (x) | x ∈ Nk } is a solid code.

For the special case of k = 0, N0 is either empty or the set consisting of

the empty tuple. Hence, |f0 (N0 )| and |g0 (N0 )| are both 0 or both 1. Thus
|C ∩ 0+ 1+ | ≤ 1. This fact is also proved in [64].
By Lemma 11.1, a solid code in (0+ 1+ )+ is uniquely given by a triple
(N, f, g). Note that, even when Sol(N, f, g) is true, the language correspond-
ing to such a triple need not be a solid code. This is so, because the solidity
condition does not concern the interaction between different components of
N . For our purpose this is not causing a serious problem as, in all subsequent
applications of Lemma 11.1, N0 and N1 are the only potentially non-empty
components of N .
 Codes 83

Theorem 11.8 [55] Let X = {0, 1} and let C ⊆ 0+ 1+ ∪ 0+ 1+ 0+ 1+ . For

k ∈ N0 let

Nk = {(j1 , i1 , j2 , i2 , . . . , jk , ik ) | C ∩ 0+ 1j1 0i1 1j2 0i2 · · · 1jk 0ik 1+ 6= ∅}.

Then C is a solid code which is not a proper subset of a solid code C 0 ⊆

0+ 1+ ∪0+ 1+ 0+ 1+ if and only if there are sequences f and g as in Lemma 11.1
and C is of one of the following forms:
0: N0 = {()}, N1 = N2 = . . . = ∅, f0 () = 1 or g0 () = 1.
FF: N0 = {()}, f0 () > 1, g0 () > 1, N1 = {1, . . . , g0 () − 1} × {1, . . . , f0 () − 1},
N2 = N3 = . . . = ∅, and Sol(N, f, g).
II: N0 = ∅, N1 = N × N, N2 = N3 = . . . = ∅, and Sol(N, f, g).
IF: N0 = ∅, N1 = {1, . . . , m − 1} × N for some m > 1, N2 = N3 = . . . = ∅,
and Sol(N, f, g) such that there are infinitely many i with g1 (j, i) = m
for some j.
FI: N0 = ∅, N1 = N × {1, . . . , n − 1} for some n > 1, N2 = N3 = . . . = ∅,
and Sol(N, f, g) such that there are infinitely many j with f1 (j, i) = n
for some i.
Using Theorem 11.8, one can characterize the maximal solid codes C in
0+ 1+ ∪ 0+ 1+ 0+ 1+ . This characterization again distinguishes the 5 types 0,
FF, II, IF, and FI.
Theorem 11.9 [55] Let X = {0, 1} and let C ⊆ 0+ 1+ ∪ 0+ 1+ 0+ 1+ , C 6= ∅.
For k ∈ N0 let

Nk = {(j1 , i1 , j2 , i2 , . . . , jk , ik ) | C ∩ 0+ 1j1 0i1 1j2 0i2 · · · 1jk 0ik 1+ 6= ∅}.

Then C is a maximal solid code over X if and only if there are sequences f
and g as in Lemma 11.1 and C satisfies one of the following conditions:
(1) C is of type 0.
(2) C is of one of the types FF, II, IF, or FI, f1 (j, i) is independent of i and
increasing with j, g1 (j, i) is independent of j and increasing with i, and
f1 and g1 determine each other uniquely. Moreover, for (j, i) ∈ N1 , let

Gi = {l | (l, i) ∈ N1 , f1 (l, i) > i}

and
Fj = {l | (j, l) ∈ N1 , g1 (j, l) > j}.
The mappings f1 and g1 have the following properties depending on the
type of C:
(a) Type FF with n = f0 () and m = g0 (): For all (j, i) ∈ N1 ,
½
min Gi , if Gi 6= ∅,
g1 (j, i) =
m, otherwise,
84 H. Jürgensen and S. Konstantinidis

f1 (j, i) ≤ n, and g1 (j, i) ≤ m.

(b) Type II: For all (j, i) ∈ N1 , g1 (j, i) = min Gi , and

lim f1 (l, i) = lim g1 (j, l) = ∞.

l→∞ l→∞

(c) Type IF with N1 = {1, . . . , m − 1} × N: For all (j, i) ∈ N1 , f1 (j, i) =

min Fj , g1 (j, i) ≤ m, liml→∞ g1 (j, l) = m.
(d) Type FI with N1 = N × {1, . . . , n − 1}: For all (j, i) ∈ N1 , g1 (j, i) =
min Gi , f1 (j, i) ≤ n, liml→∞ f1 (l, i) = n.
Moreover, suppose N = (N0 , N1 , ∅, . . .), f0 , and g0 have the properties re-
quired by one of the types FF, II, IF, or FI. If f1 and g1 have the correspond-
ing properties in condition (2), then Sol(N, f, g) where f = (f0 , f1 , . . .) and
g = (g0 , g1 , . . .).
Note that in Theorem 11.9 one also has
½
min Fj , if Fj 6= ∅,
f1 (j, i) =
n, otherwise,

in the case (2a) and f1 (j, i) = min Fj in the case (2b). This follows by duality.
By Theorem 11.9, there is a maximal solid code C ⊆ 0+ 1+ ∪ 0+ 1+ 0+ 1+
with k = |C| for every k ∈ N. A maximal solid code of type 0 has exactly 1
element. For k > 1, a maximal solid code of type FF with n = 2 and m = k
has exactly k elements [55].
The following theorem describes the relation of the class of maximal solid
codes in the set 0+ 1+ ∪ 0+ 1+ 0+ 1+ to the classical Chomsky hierarchy of
formal languages.
Theorem 11.10 [55] Let X = {0, 1} and let C ⊆ 0+ 1+ ∪ 0+ 1+ 0+ 1+ be a
maximal solid code. The following statements hold true:
(1) C is finite if and only if C is of type 0 or FF.
(2) C is regular if and only if it is of one of the types 0, FF, IF, or FI.
Moreover, there exist infinitely many infinite regular maximal solid codes
in 0+ 1+ 0+ 1+ .
(3) If C is context-free, but not regular, then C is of type II. Moreover,
there exist infinitely many context-free, non-regular maximal solid codes
in 0+ 1+ 0+ 1+ .
For the remaining statements assume that C is of type II and

C = {0ϕ(j) 1j 0i 1γ(i) | j, i ∈ N}.

(4) The following conditions on C are equivalent:

(a) ϕ is recursive.
(b) γ is recursive.
(c) C is recursively enumerable.
 Codes 85

(d) C is recursive.
(5) There are infinitely many maximal solid codes which are context-sensi-
tive, but not context-free.
(6) There is a maximal solid code in 0+ 1+ 0+ 1+ which is not recursively
enumerable.
Our final theorem in this section relates maximal solid codes to prefix
codes and suffix codes.
Theorem 11.11 [55] Let X = {0, 1} and let C ⊆ 0+ 1+ ∪ 0+ 1+ 0+ 1+ be an
infinite maximal solid code. Then C = P S where P and S are contained in
0+ 1+ and satisfy the following conditions.
(1) If C is of type II then P is an infinite suffix code and S is an infinite
prefix code.
(2) If C is of type IF then P is a finite suffix code and S is an infinite prefix
code.
(3) If C is of type FI then P is an infinite suffix code and S is a finite prefix
code.

12. Codes for noisy channels

In this section we discuss some aspects of coding for noisy channels. The
presentation is relatively informal as it is meant to point out problems rather
than present solutions.
A message received via a noisy channel may be distorted in many ways
depending on the physical properties of the channel and sometimes also on
the structure of the message.48 Thus, a model of the physical channel needs
to be known before an appropriate code can be chosen.
For example, if the channel is known to substitute signals with some prob-
ability greater than 0, but to keep synchronization intact with probability 1,
one may decide to use a uniform code K of word length n, say. If w ∈ K
is sent and w 0 is received then w 0 is assumed to have the correct length. As
synchronization errors occur with probability 0, one does not worry about
the boundaries between received words in a received message.49
Similar considerations apply to other kinds of channels. In essence, if w 0
is a received message and, for a message v, Prob(v | w 0 ) is the probability

48
For example, a channel may become saturated by a long sequence of identical
input signals and continue reproducing them for some time even after the input has
changed.
49
To be more precise, it is not really the probability of a synchronization error,
but the cost of a synchronization error that needs to be considered. Even for a
uniform code, if synchronization errors are disregarded, but can occur, albeit with
a very small probability, the cost can be devastating.
86 H. Jürgensen and S. Konstantinidis

of v having been sent when w 0 has been received, then maximum-likelihood

decoding will decode w 0 as a message w such that

Prob(w | w 0 ) > Prob(v | w 0 )

for all messages v distinct from w. In choosing a code, this is a key condition.
Channel models abstract from this probabilistic situation by eliminating all
low-probability cases.
Thus, if γ is a channel according to Section 3 then γ models only that
part of the physical channel that occurs with a high probability or results in
a high cost if it occurs; all these events are treated as equally probable; all
other events are treated as impossible, that is, not just as having probability
0. Using this idealization, one can try to replace the maximum-likelihood
decoding argument by a minimum-distance decoding argument (see [22]), that
is, replace probabilistic reasoning by combinatorial reasoning. The classical
Hamming metric and Lee metric are examples of this kind of transition for
substitution-only channels. The Levenshtein distance serves a similar purpose
for certain SID-channels. The Hamming and Lee metrics are defined for
words of the same length only: the Hamming distance between two words
is the number of positions in which they differ; the Lee metric also takes
into account by how much corresponding positions differ.50 The Levenshtein
distance between two words, u and v say, is the minimal total number of
substitutions, insertions, and deletions that can transform u into v.
If w0 is the message received when w was sent, then any distance d to be
used for minimum-distance decoding will have to satisfy

d(v, w0 ) > d(w, w 0 ) if and only if Prob(v | w 0 ) < Prob(w | w 0 )

for all messages v different from w (see [22] for further explanations). Thus,
the choice of a metric implies assumptions about the physical channel; these
are usually not made explicit in the literature. The extent to which the
assumptions are valid determines very much how well theoretical results pre-
dict physically observable behaviour. This is, of course, not unique to coding
theory; however, much of coding theory is now an area of beautiful mathe-
matical results with very little connection to the true problems in the field.
To clarify this statement: first, in the context of mathematics, there are many
wonderful and deep results derived in coding theory; second, in the context of
coding theory, however, they may be of less value as their assumptions may
be physically unrealistic. For example, very-high speed information trans-
mission via optical fibres seems to require an error model that is significantly
different from that assumed by the Hamming metric. Thus, the quality of
classical codes, as predicted in the literature, should not be taken for granted.
Much more fundamental research is needed to understand the abstract con-
nection between error models and codes to correct errors in the context of
50
See [99], for example, for precise definitions.
 Codes 87

these models. Most of coding theory, so far, has focussed on noiseless chan-
nels (the language theory branch) and channels modelled by the Hamming
metric (the error-correcting code branch).
The Hamming and Lee metrics are applicable to communication systems
in which the only likely errors are substitutions and where errors are indepen-
dent. The Levenshtein metric is applicable to physical SID-channels where
errors are independent and equally likely. Not all SID-channels – physical or
just within our formal model – have these properties.
For the abstraction from probabilities to distances, there have been two es-
sentially different techniques. The first and most common one is based on an
errors-per-code-word limit; the channel is assumed not to produce more than
k, say, errors of a certain kind per code word. This is the standard approach
in the classical theory of error-correcting codes; it is also the approach taken
in [41] and [13]. The second technique, used in our presentation, is based
on an errors-per-length limit; the channel is assumed not to produce more
than k, say, errors of a certain kind in any l consecutive input symbols. The
former is considerably easier to use;51 the latter represents many physical sit-
uations more realistically. For example, assume a block code of length l = 5
is used and the channel permits one deletion; suppose (01001)(10100) is sent.
In the errors-per-code-word model, one could get 0100× 1 ×0100
1 = 01000100
which is impossible in the errors-per-length model; on the other hand, one
can get 01001010 in both models, as 0100×101 1 ×0
0 in the former model and
as 0100×1010
1 ×
0 in both models. We believe that, for codes having only very
long code words, these two models may coincide in probability. For codes
with realistically short code words, they seem to be vastly different.
As mentioned before, solid codes seem to be extremely good at synchro-
nizing in the presence of errors – any code word transmitted correctly will be
decoded correctly. They are not good enough in general, however, to correct
incorrectly transmitted parts of a message; in those parts, they detect that
errors are present, but do not guide the correction.
For example, suppose the only errors that are reasonably likely to oc-
cur are deletions of symbols; these are independent; and it is, by any stan-
dards, completely unlikely that there will be more than 1 deletion in any l
consecutive message symbols. The corresponding (abstract) channel is the
SID-channel δ(1, l) which permits at most 1 deletion in any l consecutive
symbols [59]. Let M = (N \ {1}) × (N \ {1}) and let F be the set
½ ¯ ¾
¯ x, y ∈ N \ {1}, x 6= y, fx,y : M → N,
F = fx,y ¯ ¯ .
fx,y (r1 , r2 ) = xr1 + yr2 for (r1 , r2 ) ∈ M
For f ∈ F and n ∈ N \ {1}, let
Gf (n) = {r1 | (r1 , r2 ) ∈ M, f (r1 , r2 ) ≤ n}.
51
See the admissibility problems in our definitions of synchronization and decod-
ability, Definition 4.2 and Definition 4.4, which are a result of the fact that error
situations do not know about the ends of code words.
88 H. Jürgensen and S. Konstantinidis

Using properties explained in Section 11, one can construct codes for the
channel δ(1, l) as follows.
Theorem 12.1 [57] Let f ∈ F and g : M → N \ {1} such that, for all
r = (r1 , r2 ) ∈ M, g(r) > max Gf (r2 ). Let

K = {0f (r1 ,r2 ) 1r2 0r1 1g(r1 ,r2 ) | (r1 , r2 ) ∈ M}.

Then K is a solid code. If K 0 is a finite subset of K and l is the maximal

length of a word in K 0 then K 0 is right δ(1, l)-decodable.

Example 12.1 The language

{02r1 +3r2 1r2 0r1 1br1 /2c+1 | (r1 , r2 ) ∈ M}

satisfies the conditions of Theorem 12.1.

In Example 4.1(3), a two-word code is given which is (γ, ζ)-correcting for
γ = δ(1, 5); That code is not a solid code.
The code words in error-correcting solid codes for SID-channels are quite
long; this is undesirable, but could be inevitable. The lower bound of The-
orem 11.5(3) does not take error-correction into account. The redundancy
– as introduced in Section 11 – of the language in Example 12.1, assum-
52
ing
√ the words are ordered by increasing length, is asymptotically equal to
1
2 112n − log n.
Most work on error-correcting codes for SID-channels has concentrated
on block codes, often restricted to the cases of insertion and deletion errors
– sometimes referred to as synchronization errors.53 In [133], block codes
of length m, with m < n + log2 n + 4, for encoding words of length n are
constructed which are (γ, ∗)-correcting for the channel γ = (ι ¯ δ)(1, m +
2). Moreover, it is shown in [134] that, asymptotically, n + log 2 n + 1 is
a lower bound on the achievable length. The codes of [133] are not solid,
in general. Non-block codes have been studied even less in the context of
error-correction.54
Beyond the classical problems of coding theory, discussed in part in ear-
lier sections of this chapter, the presence of noise raises several additional
fundamental issues:
52
To prove this, first note that the code words have lengths 3r1 + 4r2 + b r21 c + 1
with r1 , r2 ∈ N\{1}. Let ν(l) be the number of code words of length l, where l ≥ 16.
l l
One shows, with a case distinction according to l mod 4, that 14 −1 ≤ ν(l) ≤ 14 +1.
Pl−1
The integer n is mapped onto a code word of length √
l if and only if i=16
√
ν(i) ≤
n < li=16 ν(i). Combining this, one obtains −29+ 112n+3481 29+ 112n+9
P
2 < l < 2 .
1√ 31 1√ 27
Thus, 2 112n + 3481 − log n − 2 < %(n) ≤ 2 112n + 9 − log n + 2 , hence
√
%(n) ∼ 21 112n − log n.
53
[122], [133], [141], [80], [79], [81], [83], [86], [112], [87], [10],[41], [5].
54
[102], [45], [59], [57], [58], [70], [13], [41].
 Codes 89

• For restricted classes of channels, like SID-channels, determine construc-

tions of classes of codes which are error-correcting, decodable, uniformly
synchronous, and efficient.55
• For SID-channels and in terms of the channel parameters, describe good
upper and lower bounds on redundancy.56
• For SID-channels, determine which type of constraint – expressed as in-
dependence or in some other systematic formal manner – addresses which
error-correction, decodability, or synchronizability problems.
This type of questions is unsolved even for substitution-only channels. 57
Moreover, it seems that these considerations will have to focus on classes
of codes in the intersection Li ∩ Lo ∩ L, where L is a family of languages
which is slightly larger than, but very similar to Lol-free .
SID-channels, while more realistic than substitution-only channels, are
not likely to be adequate for modelling even just the noisy channels arising
in present communication technology. We believe that the framework of
P-channels is general enough to model many physically realizable channels.
However, the following fundamental problems need answers:
• Good and simple channel models for existing communications technology
need to be developed, and a programme has to be carried out for these,
similar to the one described for SID-channels.58
• The model of P-channels, the channel model used in the classical theory
of error-correcting codes, and the models assumed in [41] and [13] need to
be unified.
• A method for abstracting relevant mathematical channel models from phys-
ical channels needs to be developed.59
This list of problems is by no means complete. Given the experience of coding
theory so far, pursuing any one of them will be very difficult.

55
Efficiency may be achieved through small redundancy or small complexity of
encoding and decoding, for example.
56
For block codes and substitution-only channels, the Hamming bound and the
Gilbert-Varshamov bound are examples of such bounds; see [94].
57
In the absence of synchronization errors, block codes – of course – are easier to
implement; and, asymptotically, they are as efficient as non-block codes.
58
As a nearly randomly selected example, we mention the problems arising in
optical data transmission when overlapping pulse-position modulation is used for
the physical representation of signals; see [11] for details.
59
Of course, this question is ill-posed. However, even slight progress along these
lines could be extremely important for our understanding of communication systems.
90 H. Jürgensen and S. Konstantinidis

13. Concluding remarks

As mentioned before, the theory of codes has, essentially, three nearly unre-
lated branches. In writing this handbook chapter, while focussing on aspects
of the theory of formal languages, we attempted to provide an overview which
includes aspects of all three branches. As much of the language theoretic work
on codes is well represented in book form, except, of course, some quite re-
cent results, we decided to focus on general structural issues and on issues
concerning codes for noisy channels. We attempted a unified presentation
of the theory, hoping that we might succeed in exposing many unanswered
questions, albeit sometimes implicitly.
Natural languages are quite fault-tolerant; they have enormous error-
correction capabilities. In this spirit, we believe the notion of error-correction
deserves a focal spot in the theory of formal languages.

References
[1] R. Ahlswede, I. Wegener: Suchprobleme. B. G. Teubner, Stuttgart, 1979.
[2] L. R. Bahl, F. Jelinek: Decoding for channels with insertions, deletions, and
substitutions with applications to speech recognition. IEEE Trans. Inform.
Theory IT-21 (1975), 404–411.
[3] L. R. Bahl, F. Jelinek, R. L. Mercer: A maximum likelihood approach to
continuous speech recognition. IEEE Trans. Pattern Analysis and Machine
Intell. 5 (1983), 179–190.
[4] J. Berstel, D. Perrin: Theory of Codes. Academic Press, Orlando, 1985.
[5] P. A. H. Bours: Construction of fixed-length insertion/deletion correcting
runlength-limited codes. IEEE Trans. Inform. Theory IT-40 (1994), 1841–
1856.
[6] V. Bruyère: Maximal prefix products. Semigroup Forum 36 (1987), 147–157.
[7] V. Bruyère: Maximal codes with bounded deciphering delay. Theoret. Com-
put. Sci. 84 (1991), 53–76.
[8] V. Bruyère, M. Latteux: Variable-length maximal codes. In F. Meyer auf der
Heide, B. Monien (editors): Automata, Languages and Programming, 23rd
International Colloquium, ICALP ’96, Paderborn, Germany, July 1996, Pro-
ceedings. Lecture Notes in Computer Science 1099, 24–47, Springer-Verlag,
Berlin, 1996.
[9] V. Bruyère, L. Wang, L. Zhang: On completion of codes with finite decipher-
ing delay. European J. Combin. 11 (1990), 513–521.
[10] L. Calabi, W. E. Hartnett: A family of codes for the correction of substitution
and synchronization errors. IEEE Trans. Inform. Theory IT-15 (1969), 102–
106.
[11] A. R. Calderbank, C. N. Georghiades: Synchronizable codes for the optical
OPPM channel. IEEE Trans. Inform. Theory IT-40 (1994), 1097–1107.
[12] R. M. Capocelli: A decision procedure for finite decipherability and syn-
chronizability of multivalued encodings. IEEE Trans. Inform. Theory IT-28
(1982), 307–318.
[13] R. M. Capocelli, L. Gargano, U. Vaccaro: Decoders with initial state invari-
ance for multivalued encodings. Theoret. Comput. Sci. 86 (1991), 365–375.
 Codes 91

[14] R. M. Capocelli, C. M. Hoffmann: Algorithms for factorizing and testing

subsemigroups. In A. Apostolico, Z. Galil (editors): Combinatorial Algorithms
on Words. NATO ASI Series F12, 59–81, Springer-Verlag, Berlin, 1985.
[15] R. M. Capocelli, U. Vaccaro: Structure of decoders for multivalued encodings.
Discrete Appl. Math. 23 (1989), 55–71.
[16] P. M. Cohn: Universal Algebra. D. Reidel Publishing Co., Dordrecht, revised
ed., 1981.
[17] W. Damm: The IO- and OI-hierarchies. Theoret. Comput. Sci. 20 (1982),
95–206.
[18] P. H. Day, H. J. Shyr: Languages defined by some partial orders. Soochow
J. Math. 9 (1983), 53–62.
[19] J. Devolder: Precircular codes and periodic biinfinite words. Inform. and
Comput. 107 (1993), 185–201.
[20] J. Devolder, M. Latteux, I. Litovsky, L. Staiger: Codes and infinite words.
Acta Cybernet. 11 (1994), 241–256.
[21] J. Devolder, E. Timmerman: Finitary codes for bi-infinite words. RAIRO
Inform. Théor. Appl. 26 (1992), 363–386.
[22] J. Duske, H. Jürgensen: Codierungstheorie. BI Wissenschaftsverlag, Mann-
heim, 1977.
[23] A. Ehrenfeucht, G. Rozenberg: Each regular code is included in a maximal
regular code. RAIRO Inform. Théor. Appl. 20 (1985), 89–96.
[24] Eilenberg: Automata Languages and Machines, Volume A. Academic Press,
New York, 1974.
[25] J. Engelfriet: Iterated stack automata and complexity classes. Inform. and
Comput. 95 (1991), 21–75.
[26] J. Engelfriet, H. Vogler: Pushdown machines for the macro tree transducer.
Theoret. Comput. Sci. 42 (1986), 251–368.
[27] J. Engelfriet, H. Vogler: Look-ahead on pushdowns. Inform. and Comput. 73
(1987), 245–279.
[28] J. Engelfriet, H. Vogler: High level tree transducers and iterated pushdown
tree transducers. Acta Inform. 26 (1988), 131–192.
[29] C. de Felice: Construction of a family of finite maximal codes. Theoret.
Comput. Sci. 63 (1989), 157–184.
[30] C. de Felice, A. Restivo: Some results on finite maximal codes. RAIRO
Inform. Théor. Appl. 19 (1985), 383–403.
[31] F. Gécseg, H. Jürgensen: Dependence in algebras. Fund. Inform. To appear.
[32] F. Gécseg, H. Jürgensen: Algebras with dimension. Algebra Universalis 30
(1993), 422–446.
[33] Y. V. Glebskii: Coding by means of finite automata. Dokl. Akad. Nauk. SSSR
141 (1961), 1054–1057, in Russsian. English translation: Soviet Physics Dokl.
6 (1962), 1037–1039.
[34] G. Grätzer: Universal Algebra. Van Nostrand, Princeton, NJ, 1968.
[35] S. A. Greibach: A remark on code sets and context-free languages. IEEE
Trans. Comput. C-24 (1975), 741–742.
[36] S. Guiaşu: Information Theory with Applications. McGraw-Hill, London,
1977.
[37] C. G. Günther: A universal algorithm for homophonic coding. In C. G.
Günther (editor): Advances in Cryptology—Proceedings of Eurocrypt’88,
Workshop on the Theory and Application of Cryptographic Techniques,
92 H. Jürgensen and S. Konstantinidis

Davos, 1988. Lecture Notes in Computer Science 330, 405–414, Springer-

Verlag, Berlin, 1988.
[38] Y. Q. Guo, H. J. Shyr, G. Thierrin: e-convex infix codes. Order 3 (1986),
55–59.
[39] Y. Q. Guo, G. Thierrin, S. H. Zhang: Semaphore codes and ideals. J. Inform.
Optim. Sci. 9(1) (1988), 73–83.
[40] W. E. Hartnett: Generalization of tests for certain properties of variable-
length codes. Inform. and Control 13 (1968), 20–45.
[41] W. E. Hartnett (editor): Foundations of Coding Theory. Boston, 1974. D. Rei-
del Publishing Co.
[42] T. Head, G. Thierrin: Hypercodes in deterministic and slender OL languages.
Inform. and Control 45(3) (1980), 251–262.
[43] T. Head, A. Weber: Deciding code related properties by means of finite
transducers. In R. Capocelli, A. de Santis, U. Vaccaro (editors): Sequences II,
Methods in Communication, Security, and Computer Science. 260–272, Sprin-
ger-Verlag, Berlin, 1993.
[44] C. M. Hoffmann: A note on unique decipherability. In M. P. Chytil, V. Koubek
(editors): Mathematical Foundations of Computer Science 1984; Proceedings,
11th Symposium; Praha, Czechoslovakia; September 3–7, 1984. Lecture Notes
in Computer Science 176, 50–63, Springer-Verlag, Berlin, 1984.
[45] H. D. L. Hollman: A relation between Levenshtein-type distances and
insertion-and-deletion correcting capabilities of codes. IEEE Trans. Inform.
Theory IT-39 (1993), 1424–1427.
[46] O. H. Ibarra: Reversal-bounded multicounter machines and their decision
problems. J. Assoc. Comput. Mach. 25 (1978), 116–133.
[47] M. Ito, H. Jürgensen: Shuffle relations. Manuscript, 1996. In preparation.
[48] M. Ito, H. Jürgensen, H. J. Shyr, G. Thierrin: Anti-commutative languages
and n-codes. Discrete Appl. Math. 24 (1989), 187–196.
[49] M. Ito, H. Jürgensen, H. J. Shyr, G. Thierrin: n-Prefix-suffix languages.
Internat. J. Comput. Math. 30 (1989), 37–56.
[50] M. Ito, H. Jürgensen, H. J. Shyr, G. Thierrin: Outfix and infix codes and
related classes of languages. J. Comput. System Sci. 43 (1991), 484–508.
[51] M. Ito, H. Jürgensen, H. J. Shyr, G. Thierrin: Languages whose n-element
subsets are codes. Theoret. Comput. Sci. 96 (1992), 325–344.
[52] M. Ito, G. Thierrin: Congruences, infix and cohesive prefix codes. Theoret.
Comput. Sci. 136 (1994), 471–485.
[53] H. N. Jendal, Y. J. B. Kuhn, J. L. Massey: An information-theoretic treat-
ment of homophonic substitution. In J.-J. Quisquater, J. Vandewalle (edi-
tors): Advances in Cryptology—Proceedings of Eurocrypt’89, Workshop on
the Theory and Application of Cryptographic Techniques, Houthalen, 1989.
Lecture Notes in Computer Science 434, 382–394, Springer-Verlag, Berlin,
1989.
[54] H. Jürgensen: Syntactic monoids of codes. Report 327, Department of Com-
puter Science, The University of Western Ontario, 1992.
[55] H. Jürgensen, M. Katsura, S. Konstantinidis: Maximal solid codes. Manu-
script, 1996. In Preparation.
[56] H. Jürgensen, S. Konstantinidis: The hierarchy of codes. In Z. Ésik (editor):
Fundamentals of Computation Theory, 9th International Conference, FCT’93.
Lecture Notes in Computer Science 710, 50–68, Springer-Verlag, Berlin, 1993.
 Codes 93

[57] H. Jürgensen, S. Konstantinidis: Variable-length codes for error correction.

In Z. Fülöp, F. Gécseg (editors): Automata, Languages and Programming,
22nd International Colloquium, ICALP95, Proceedings. Lecture Notes in
Computer Science 944, 581–592, Springer-Verlag, Berlin, 1995.
[58] H. Jürgensen, S. Konstantinidis: Burst error correction for channels with
substitutions, insertions and deletions. Manuscript, 1996. In preparation.
[59] H. Jürgensen, S. Konstantinidis: Error correction for channels with sub-
stitutions, insertions, and deletions. In J.-Y. Chouinard, P. Fortier, T. A.
Gulliver (editors): Information Theory and Applications 2, Fourth Canadian
Workshop on Information Theory. Lecture Notes in Computer Science 1133,
149–163, Springer-Verlag, Berlin, 1996.
[60] H. Jürgensen, L. Robbins: Towards foundations of cryptography: Investiga-
tion of perfect secrecy. J. UCS 2 (1996), 347–379. Special issue: C. Calude
(ed.), The Finite, the Unbounded and the Infinite, Proceedings of the Summer
School “Chaitin Complexity and Applications,” Mangalia, Romania, 27 June
– 6 July, 1995.
[61] H. Jürgensen, K. Salomaa, S. Yu: Decidability of the intercode property.
J. Inform. Process. Cybernet., EIK 29 (1993), 375–380.
[62] H. Jürgensen, K. Salomaa, S. Yu: Transducers and the decidability of inde-
pendence in free monoids. Theoret. Comput. Sci. 134 (1994), 107–117.
[63] H. Jürgensen, G. Thierrin: Infix codes. In M. Arató, I. Kátai, L. Varga (edi-
tors): Topics in the Theoretical Bases and Applications of Computer Science,
Proceedings of the 4th Hungarian Computer Science Conference, Györ, 1985.
25–29, Akadémiai Kiadó, Budapest, 1986.
[64] H. Jürgensen, S. S. Yu: Solid codes. J. Inform. Process. Cybernet., EIK 26
(1990), 563–574.
[65] H. Jürgensen, S. S. Yu: Relations on free monoids, their independent sets,
and codes. Internat. J. Comput. Math. 40 (1991), 17–46.
[66] H. Jürgensen, S. S. Yu: Dependence systems and hierarchies of families of
languages. Manuscript, 1996. In preparation.
[67] D. Kahn: The Codebreakers. Macmillan Publishing Co., New York, 1967.
[68] J. Karhumäki: On three-element codes. In J. Paredaens (editor): Automata,
Languages and Programming, 11th International Colloquium, ICALP 1984,
Proceedings. Lecture Notes in Computer Science 172, 292–302, Springer-
Verlag, Berlin, 1984.
[69] J. Karhumäki: On three-element codes. Theoret. Comput. Sci. 40 (1985),
3–11.
[70] S. Konstantinidis: Error Correction and Decodability. Ph. D. thesis, The
University of Western Ontario, London, Canada, 1996.
[71] G. Lallement: Semigroups and Combinatorial Applications. John Wiley &
Sons, Inc., New York, 1979.
[72] N. H. Lâm, D. L. Van: On a class of infinitary codes. RAIRO Inform. Théor.
Appl. 24 (1990), 441–458.
[73] J. L. Lassez: Circular codes and synchronization. Internat. J. Comput. Inform.
Sci. 5 (1976), 201–208.
[74] V. I. Levenshtein: Certain properties of code systems. Dokl. Akad. Nauk.
SSSR 140 (1961), 1274–1277, in Russian. English translation: Soviet Physics
Dokl. 6 (1962), 858–860.
94 H. Jürgensen and S. Konstantinidis

[75] V. I. Levenshtein: Self-adaptive automata for decoding messages. Dokl. Akad.

Nauk. SSSR 141 (1961), 1320–1323, in Russian. English translation: Soviet
Physics Dokl. 6 (1962), 1042–1045.
[76] V. I. Levenshtein: The inversion of finite automata. Dokl. Akad. Nauk. SSSR
147 (1962), 1300–1303, in Russian. English translation: Soviet Physics Dokl.
7 (1963), 1081–1084.
[77] V. I. Levenshtein: Decoding automata, invariant with respect to the initial
state. Problemy Kibernet. 12 (1964), 125–136, in Russian.
[78] V. I. Levenshtein: Some properties of coding and self-adjusting automata
for decoding messages. Problemy Kibernet. 11 (1964), 63–121, in Russian.
German translation: Über einige Eigenschaften von Codierungen und von
selbstkorrigierenden Automaten zur Decodierung von Nachrichten, Probleme
der Kybernetik 7 (1966), 96–163. An English translation is available from
the Clearinghouse for Federal Scientific and Technical Information, U. S. De-
partment of Commerce, under the title Problems of Cybernetics, Part II,
document AD 667 849; it was prepared as document FTD-MT-24-126-67 by
the Foreign Technology Division, U. S. Air Force.
[79] V. I. Levenshtein: Binary codes capable of correcting deletions, insertions,
and reversals. Dokl. Akad. Nauk. SSSR 163 (1965), 845–848, in Russian.
English translation: Soviet Physics Dokl. 10 (1966), 707–710.
[80] V. I. Levenshtein: Binary codes capable of correcting spurious insertions
and deletions of ones. Problemy Peredachi Informatsii 1(1) (1965), 12–25,
in Russian. English translation: Problems Inform. Transmission 1(1) (1966),
8–17.
[81] V. I. Levenshtein: Asymptotically optimum binary code with correction for
losses of one or two adjacent bits. Problemy Kibernet. 19 (1967), 293–298, in
Russian. English translation: Systems Theory Research 19 (1970), 298–304.
[82] V. I. Levenshtein: On the redundancy and delay of decodable coding of
natural numbers. Problemy Kibernet. 20 (1968), 173–179, in Russian. English
translation: Systems Theory Research 20 (1971), 149–155.
[83] V. I. Levenshtein: Bounds for codes ensuring error correction and synchroniza-
tion. Problemy Peredachi Informatsii 5(2) (1969), 3–13, in Russian. English
translation: Problems Inform. Transmission 5(2) (1969), 1–10.
[84] V. I. Levenshtein: Maximum number of words in codes without overlaps.
Problemy Peredachi Informatsii 6(4) (1970), 88–90, in Russian. English trans-
lation: Problems Inform. Transmission 6(4) (1973), 355–357.
[85] V. I. Levenshtein: One method of constructing quasilinear codes providing
synchronization in the presence of errors. Problemy Peredachi Informatsii
7(3) (1971), 30–40, in Russian. English translation: Problems Inform. Trans-
mission 7(3) (1973), 215–222.
[86] V. I. Levenshtein: On perfect codes in deletion and insertion metric. Diskret.
Mat. 3 (1991), 3–20, in Russian. English translation: Discrete Math. Appl.
2 (1992), 241–258.
[87] J. E. Levy: Self-synchronizing codes derived from binary cyclic codes. IEEE
Trans. Inform. Theory IT-12 (1966), 286–290.
[88] B. E. Litow: Parallel complexity of the regular code problem. Inform. and
Comput. 86 (1990), 107–114.
[89] D. Y. Long: k-Outfix codes. Chinese Ann. Math. Ser. A 10 (1989), 94–99, in
Chinese.
 Codes 95

[90] D. Y. Long: k-Prefix codes and k-infix codes. Acta Math. Sinica 33 (1990),
414–421, in Chinese.
[91] D. Y. Long: n-Infix-outfix codes. In Abstracts, Second International Collo-
quium on Words, Languages, and Combinatorics, Kyoto, 25–28 August, 1992.
50–51, Kyoto, 1992.
[92] D. Y. Long: On the structure of some group codes. Semigroup Forum 45
(1992), 38–44.
[93] D. Y. Long: k-Bifix codes. Riv. Mat. Pura Appl. 15 (1994), 33–55.
[94] F. J. MacWilliams, N. J. A. Sloane: The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977, 2 vols.
[95] A. A. Markov: Some properties of infinite prefix codes. Problemy Peredachi
Informatsii 6(1) (1970), 97–98, in Russian. English translation: Problems
Inform. Transmission 6(1) (1973), 85–87.
[96] P. G. Neumann: Codes auf der Grundlage von Schaltfunktionen und ihre An-
wendung in der Praxis der Verschlüsselung. Nachrichtentechn. Z. 14 (1961),
254–261, 307–312.
[97] P. G. Neumann: Efficient error-limiting variable-length codes. IEEE Trans.
Inform. Theory IT-8 (1962), 292–304.
[98] P. G. Neumann: Error-limiting coding using information-lossless sequential
machines. IEEE Trans. Inform. Theory IT-10 (1964), 108–115.
[99] W. W. Peterson, E. J. Weldon, Jr.: Error-Correcting Codes. MIT Press,
Cambridge, MA, second ed., 1972.
[100] M. Petrich: Lectures in Semigroups. Akademie-Verlag, Berlin, 1977.
[101] M. Petrich, G. Thierrin: The syntactic monoid of an infix code. Proc. Amer.
Math. Soc. 109 (1990), 865–873.
[102] P. Piret: Comma free error correcting codes of variable length, generated by
finite-state encoders. IEEE Trans. Inform. Theory IT-28 (1982), 764–775.
[103] T. Pratt, W. C. Bostian: Satellite Communications. John Wiley & Sons, New
York, 1986.
[104] H. Prodinger, G. Thierrin: Towards a general concept of hypercodes. J.
Inform. Optim. Sci. 4 (1983), 255–268.
[105] C. M. Reis: Intercodes and the semigroups they generate. Internat. J. Com-
put. Math. 51 (1994), 7–13.
[106] C. M. Reis, G. Thierrin: Reflective star languages and codes. Inform. and
Control 42 (1979), 1–9.
[107] A. Restivo: A combinatorial property of codes having finite synchronization
delay. Theoret. Comput. Sci. 1 (1975), 95–101.
[108] A. Restivo: On codes having no finite completions. Discrete Math. 17 (1977),
309–316.
[109] A. Restivo, S. Salemi, T. Sportelli: Completing codes. RAIRO Inform. Théor.
Appl. 23 (1989), 135–147.
[110] A. Riley: The Sardinas-Patterson and Levenshtein theorems. Inform. and
Control 10 (1967), 120–136.
[111] O. T. Romanov: Invariant decoding automata without look-ahead. Problemy
Kibernet. 17 (1966), 233–236, in Russian.
[112] R. M. Roth, P. H. Siegel: Lee-metric BCH codes and their application to
constrained and partial-response channels. IEEE Trans. Inform. Theory IT-
40 (1994), 1083–1096.
96 H. Jürgensen and S. Konstantinidis

[113] J. Sakarovitch: Un cadre algébrique pour l’étude des monoı̈des syntactiques.

In Séminaire P. Dubreil (Algèbre), 28e année. 14. Paris, 1974/75.
[114] K. Salomaa. Personal communication, 1996.
[115] A. A. Sardinas, C. W. Patterson: A necessary and sufficient condition for the
unique decomposition of coded messages. IRE Intern. Conven. Rec. 8 (1953),
104–108.
[116] K. Sato: Decipherability of GSM encoding. Denshi Tsushin Gakkai Ronbunshi
57-D (1974), 181–188, in Japanese. English translation: Systems-Computers-
Controls 5 (1974), 53–61.
[117] K. Sato: A decision procedure for the unique decipherability of multivalued
encodings. IEEE Trans. Inform. Theory IT-25 (1979), 356–360.
[118] M. Satyanarayana: Uniformly synchronous codes. Semigroup Forum 46
(1993), 246–252.
[119] M. Satyanarayana, S. Mohanty: Limited semaphore codes. Semigroup Forum
45 (1992), 367–371.
[120] M. Satyanarayana, S. Mohanty: Uniformly synchronous limited codes. Semi-
group Forum 46 (1993), 21–26.
[121] B. M. Schein: Homomorphisms and subdirect decompositions of semigroups.
Pacific J. Math. 17 (1966), 529–547.
[122] F. F. Sellers, Jr.: Bit loss and gain correction code. IRE Trans. Inform.
Theory IT-8 (1962), 35–38.
[123] H. J. Shyr: Free Monoids and Languages. Hon Min Book Company, Taichung,
second ed., 1991.
[124] H. J. Shyr, G. Thierrin: Hypercodes. Inform. and Control 24 (1974), 45–54.
[125] H. J. Shyr, S. S. Yu: Intercodes and some related properties. Soochow J. Math.
16 (1990), 95–107.
[126] H. J. Shyr, S. S. Yu: Solid codes and disjunctive domains. Semigroup Forum
41 (1990), 23–37.
[127] J. C. Spehner: Quelques constructions et algorithmes relatifs aux sous-
monoı̈des d’un monoı̈de libre. Semigroup Forum 9 (1975), 334–353.
[128] L. Staiger: On infinitary finite length codes. RAIRO Inform. Théor. Appl.
20 (1986), 483–494.
[129] G. Tenengol’ts: Nonbinary codes, correcting single deletion or insertion. IEEE
Trans. Inform. Theory IT-30 (1984), 766–769.
[130] G. Thierrin: Hypercodes, right convex languages and their syntactic monoids.
Proc. Amer. Math. Soc. 83(2) (1981), 255–258.
[131] G. Thierrin: The syntactic monoid of a hypercode. Semigroup Forum 6
(1973), 227–231.
[132] G. Thierrin, S. S. Yu: Shuffle relations and codes. J. Inform. and Optim. Sci.
12 (1991), 441–449.
[133] J. D. Ullman: Near-optimal, single-synchronization-error-correcting code.
IEEE Trans. Inform. Theory IT-12 (1966), 418–424.
[134] J. D. Ullman: On the capabilities of codes to correct synchronization errors.
IEEE Trans. Inform. Theory IT-13 (1967), 95–105.
[135] E. Valkema: Syntaktische Monoide und Hypercodes. Semigroup Forum 13
(1976/77), 119–126.
[136] D. L. Van: Codes avec des mots infinis. RAIRO Inform. Théor. Appl. 16
(1982), 371–386.
 Codes 97

[137] D. L. Van: Sous-monoı̈des et codes avec des mots infinis. Semigroup Forum
26 (1983), 75–87.
[138] D. L. Van: Ensembles code-compatibles et une généralisation du théorème de
Sardinas–Patterson. Theoret. Comput. Sci. 38 (1985), 123–132.
[139] D. L. Van: Langages écrits par un code infinitaire. Théorème du défaut. Acta
Cybernet. 7 (1986), 247–257.
[140] D. L. Van, D. G. Thomas, K. G. Subramanian: Bi-infinitary codes. RAIRO
Inform. Théor. Appl. 24 (1990), 67–87.
[141] R. R. Varshamov, G. M. Tenengol’ts: Codes capable of correcting single
asymmetric errors. Avtomat. i Telemekh. 26 (1965), 288–292, in Russian.
[142] M. Vincent: Construction de codes indecomposables. RAIRO Inform. Théor.
Appl. 19 (1985), 165–178.
[143] D. J. A. Welsh: Matroid Theory. Academic Press, London, 1976.
[144] S. S. Yu: A characterization of intercodes. Internat. J. Comput. Math. 36
(1990), 39–45.
[145] S. Yu. Personal communication, 1995.
[146] S. Zhang: An equivalence relation on suffix codes defined by generalized
regular languages. Internat. J. Comput. Math. 35 (1990), 15–24.

View publication stats