Publishing Partner: Cambridge University Press CUP Extra Publisher Login
amazon logo
More Info

New from Oxford University Press!


Style, Mediation, and Change

Edited by Janus Mortensen, Nikolas Coupland, and Jacob Thogersen

Style, Mediation, and Change "Offers a coherent view of style as a unifying concept for the sociolinguistics of talking media."

New from Cambridge University Press!


Intonation and Prosodic Structure

By Caroline Féry

Intonation and Prosodic Structure "provides a state-of-the-art survey of intonation and prosodic structure."

Review of  The Mathematics of Language

Reviewer: Klaus Abels
Book Title: The Mathematics of Language
Book Author: Marcus Kracht
Publisher: De Gruyter Mouton
Linguistic Field(s): Linguistic Theories
Issue Number: 16.2247

Discuss this Review
Help on Posting

Date: Fri, 15 Jul 2005 18:04:39 +0200
From: Klaus Abels
Subject: The Mathematics of Language

AUTHOR: Kracht, Marcus
TITLE: The Mathematics of Language
SERIES: Studies in Generative Grammar 63
PUBLISHER: Mouton de Gruyter
YEAR: 2003

Klaus Abels, University of Tromsø

The book presents a study of language (both natural language and formal
languages) from a mathematical perspective. It is divided into six
chapters, a bibliography, and an appendix. Each chapter is divided into
sections. All sections end with exercises for the reader and most contain
a paragraph or two of notes on the section which point out further issues,
consequences, or relevant literature. The inclusion of exercises gives the
book somewhat the appearance of a textbook. The text is aimed at formal
linguists, advanced graduate students in linguistics, in computational
linguistics, and in mathematics. A thorough understanding of the material
in Partee et al. (1993) as well as some familiarity with partial algebras
(e.g. Burmeister 2002) is required.

The first chapter, "Fundamental Structures", contains a very brief
exposition of the main mathematical tools used later in the book as well
as a very basic introduction to formal language theory. Chapter
two, "Context Free Languages", discusses the class of context free
languages, various normal forms for them, the recognition problem, parsing
strategies for context free languages, semilinearity, and, finally, the
question whether natural languages, viewed as string sets, are context
free. The famous case of Swiss German is discussed in the detail it

Chapter three, "Categorial Grammar and Formal Semantics", introduces
grammars for semiotic signs, i.e., triplets of exponents, categories, and
meanings. Kracht introduces them as systems of partial algebras. The
relevant constructs of sign grammar and system of signs are central to the
remainder of the book. After a preliminary discussion of compositionality,
Kracht goes over calculi for propositional logic and the lambda calculus,
discusses various types of categorial grammars and their generative power.
Finally Kracht offers a glimpse of Montague semantics for natural language
cast in terms of combinatory categorial grammar. In chapter
four, "Semantics", Kracht offers a perspective on some of the central
issues in semantics such as intensionality, binding and quantification,
and presupposition and partiality. Throughout he advocates an algebraic
rather than a model theoretic approach. This flows directly from his
definition of compositionality as computability in chapter three. In
chapter five, "PTIME Languages" the book returns to issues of the
complexity of natural languages but now in terms of time and space
resources rather than in terms of the complexity of rules; specifically,
Kracht explores the class of languages that are recognizable in
deterministic polynomial time and various subclasses thereof; he then
returns to the issue of compositionality; finally he introduces a novel
kind of grammar that is somewhat more parsimonious than categorial
grammars. The final chapter, "The Model Theory of Linguistic Structures",
discusses mathematical properties of various familiar proposals and
formalisms in linguistics such as complex categories, phonemes, HPSG, and
GB's chains, as well as the relation of constraint based theories to
generative theories.

The book is generally well written and clear. Among other things, it is
the valiant attempt by Kracht to bring a host of mathematical results to
the attention of a broader linguistic audience. Large parts of the book
therefore survey material that can also be found elsewhere, but because it
treats languages as systems of semiotic signs (i.e., triplets of
exponents, categories, and meanings), the book's central constructs are
much closer to linguists' everyday thinking and linguistic reality than
the constructs used and discussed in texts on formal language theory
usually are. The book is very rich and covers the mathematical foundations
for theories as diverse as Tree Adjoining Grammars, Headdriven Phrase
Structure Grammar, Government and Binging Theory, Minimalism, and
(Combinatory) Categorial Grammars. In addition, there is a lot of material
that is not found elsewhere. Especially in the later chapters Kracht also
intersperses the formal discussion with issues and problems that arise in
natural language analysis (the most unusual one probably being the
discussion of case stacking in Australian languages in section 5.1).

There are several strands of the discussion that run through the entire
book. Unsurprisingly, the question of generative power comes up at every
turn. Personally, I was particularly intrigued by Kracht's extended
discussion of compositionality. This thread is first taken up at the
beginning of chapter three. Kracht here defines a language (a set of
semiotic signs) as compositional if it has a grammar which is the
combination (the product) of three separate algebras: one for the
exponents, one for the categories, and one for the meanings. To capture
the notion of compositionality, Kracht demands that each of these grammars
have only a finite number of functions and that all functions be
computable. It is an important property of this construction that all
functions must be computable in each of the components separately. This
guarantees that each of the components is autonomous, i.e. the algebra of
exponents (roughly: phonology) is autonomous from the algebras of
categories (roughly: syntax) and of meanings (roughly: semantics) and the
latter two are autonomous from each other, too. Kracht shows that this
notion of compositionality as computability is still very weak; much
weaker in any case than the intuitive notion behind many informal
discussions of compositionality. In chapter four, however, Kracht argues
that model theoretic approaches to semantics fail even this weak notion of
compositionality as computability. Instead of a model theoretic approach,
Kracht pursues an algebraic approach to semantics paying exclusive
attention to the logical relation between sentences. Section 4.5 is
devoted entirely to an algebraic, computable treatment of variable
binding, which turns out to raise non-trivial problems. In chapter five,
section 5.7, the issue of compositionality comes up again. Here Kracht
tries to give a definition of what he calls strict compositionality which
is closer to informal usage of 'compositionality' (a system is strictly
compositional if it is strictly increasing with respect to some measure).
As a well known case where natural language has been analyzed in a way
that is not strictly compositional in this sense, he discusses Montague's
treatment of quantification. The discussion is illuminating and
worthwhile, even for readers who might not be interested in the
mathematics per se.

Despite these very positive aspects, the book has some defects as well.
Two of my complaints are purely technical and these are directed more at
the publisher than the author. As has been observed in this space before
(see, books in the Studies
in Generative Grammar series do not appear to be seriously proofread. The
text contains an annoying number of meaning-distorting typos. Books on
mathematics, where even the font often carries a heavy meaning load in
formulae, must be proofread particularly carefully. Given the steep price
of 98 euros for the book, the shoddy proofing is unacceptable. My second
technical complaint concerns the index of the book, which does not really
help the reader navigate the book. For example, the text on p. 147
contains the first mention of Presburger Arithmetic, but here it is only
mentioned in passing. The definition of Presburger Arithmetic is given on
p. 152 in a paragraph that starts: "Presburger Arithmetic is defined as
follows". Nevertheless, the index entries for Presburger Arithemtic are
only to p. 147 and p. 160 (where the term is mentioned in an exercise).
Readers unfamiliar with Presburger Arithmetic will not find this
particularly helpful. The same point can be made
regarding 'compositionality'. There are two index entries for this term:
p. X in the introduction and p. 177. The index thus does not allow the
reader to access the discussion of compositionality which follows p. 177,
it does not indicate that compositionality is centrally discussed in
sections 4.1 and 4.5 of the book, not even section 5.7
entitled 'Compositionality and Constituent Structure' can be accessed via
the index. This list can be extended ad libitum. The value of the book for
the reader would have been increased dramatically by a more comprehensive

Apart from these these technical concerns, the book, in my view, also
suffers somewhat from being over-ambitious: it aims to squeeze too much
content into too short a space.

The stated goal is to present the material in such a way that "no
particular knowledge is presupposed beyond a certain mathematical
sophistication that is in any case needed [...]" (text on back-cover).
Indeed, Kracht claims at the outset that the mathematical background
required is rather minimal: "We presuppose some familiarity with
mathematical thinking, in particular some knowledge of elementary set
theory and proof techniques such as induction" (p. 1). He further suggests
that the book is accessible even to "readers for whom [the] concepts
[algebra and structure] are entirely new" (p. 1). If this is the
readership Kracht has in mind, he obviously has to introduce quite a lot
of mathematics. To be sure, he realizes this and presumably it is this
goal of the book which explains the inclusion of exercises at the end of
each section. But despite the book's substantial length (570 pages), the
attempt at introducing the unfamiliar reader to the mathematics remains a
rudiment. There is no key to the exercises and those parts of chapter one
that might serve as an introduction are considerably denser than
comparable books in mathematics (see for comparison e.g. Volkmann (1996),
Burris and Sankappanavar (1981)). Linguists and students of linguistics
will be more familiar and comfortable with the very pedagogical style
found in Crouch and Paiva (2004) or Partee et al. (1993), and they will
almost certainly find Kracht's dense exposition of algebraic concepts off-

The difficulty in getting through the introductory part of the book is
further compounded by the fact that not all notational devices are
introduced and defined. For example the notation 'im(f)' for the range of
the function 'f ' is used in the hint to exercise one (p. 16) without
being defined anywhere. In exercise 2 on the same page, the usual ring
symbol 'o' is used to denote function composition. This symbol *has* been
introduced earlier (p. 4) but as the composition of two general relations.
In keeping with standard practice Kracht uses the ring in two different
ways for relations in general and for functions in particular. The reader
has to be made aware of this confusing, but generally accepted, notational
convention (see e.g. the cautionary note on p. 2 in Burris and
Sankappanavar (1981)). The problem with exercise 2 is that the claims the
reader is supposed to verify are false on the interpretation of the ring
as defined in the text and true only under the standard interpretation
that is not introduced anywhere in the book. Readers without enough
background to catch this might give up at this point - all others will
probably find these particular exercises superfluous. It is lamentable
that the very first exercises of the book are so impenetrable to the
uninitiated, since in most of the rest of the book, Kracht carefully
introduces his notational devices. In sum, I would not recommend reading
Kracht's book without a thorough understanding of Partee et al. (1993) and
of Burmeister (2002 up to at least p. 60). An understanding of Burmeister
(2002) is important first because most books on universal algebra treat
partial algebras with neglect and the chapter on algebras in Partee et al.
(1993) will not sufficiently equip the reader to tackle Kracht's book and
second because partial algebras play a central role as the book unfolds.

Whether or not the more introductory passages of the book are ultimately
successful, they take up space. The first two chapters alone take up more
than 170 pages although both of them contain mostly just background for
what appears to be the real project: to study languages as compositional
systems of semiotic signs. This means that the more advanced discussion is
also given short shrift; thus, Kracht hardly puts his own views of
compositionality into the context of ongoing debates surrounding the
issue, again making the text unduly compact (compare for contrast the
various manuscripts on compositionality available from Kracht's homepage

Ultimately, the beginner would have benefitted more from a good
pedagogical introduction to a selection of the issues. The more advanced
readers would have benefitted from a more thorough discussion of the
controversial and/or
novel claims made in the book. Be that as it may, readers who are willing
to unpack for themselves Kracht's dense text, will find it to be a rich
source of interesting information and inspiring thoughts.


Burmeister, Peter. 2002. Lecture notes on universal algebra: Many sorted
algebras. Available on the internet.

Burris, Stanley, and H. P. Sankappanavar. 1981. A course in universal
algebra. Graduate Texts in Mathematics. New York, Heidelberg, Berlin:

Crouch, Dick, and Valeria de Paiva. 2004. Linear logic for linguists.
Available on the Internet

Kracht, Marcus. 2003. The Mathematics of Language. Berlin: DeGruyter.

Partee, Barbara Hall, Alice ter Meulen, and Robert A. Wall. 1993.
Mathematical methods in linguistics. Dordrecht, Boston, London: Kluwer
Academic Publishers.

Volkmann, Lutz. 1996. Fundamente der Graphentheorie. Springer Lehrbuch
Mathematik. Wien: Springer.


Klaus Abels is Associate Professor of Linguistics at the University of
Tromsø. His research areas are syntax and semantics. [From --Eds.]

Amazon Store: