16.2247, Review: Mathematical Linguistics: Kracht (2003)

[LINGUIST List]

LINGUIST List: Vol-16-2247. Sun Jul 24 2005. ISSN: 1068 - 4875.

Subject: 16.2247, Review: Mathematical Linguistics: Kracht (2003)

Moderators: Anthony Aristar, Wayne State U <aristar at linguistlist.org>
            Helen Aristar-Dry, Eastern Michigan U <hdry at linguistlist.org>
 
Reviews (reviews at linguistlist.org) 
        Sheila Dooley, U of Arizona  
        Terry Langendoen, U of Arizona  

Homepage: http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, Wayne
State University, and donations from subscribers and publishers.

Editor for this issue: Naomi Ogasawara <naomi at linguistlist.org>
================================================================  

What follows is a review or discussion note contributed to our 
Book Discussion Forum. We expect discussions to be informal and 
interactive; and the author of the book discussed is cordially 
invited to join in. If you are interested in leading a book 
discussion, look for books announced on LINGUIST as "available 
for review." Then contact Sheila Dooley at collberg at linguistlist.org. 

===========================Directory==============================  

1)
Date: 24-Jul-2005
From: Klaus Abels < klaus.abels at hum.uit.no >
Subject: The Mathematics of Language 

	
-------------------------Message 1 ---------------------------------- 
Date: Sun, 24 Jul 2005 12:53:45
From: Klaus Abels < klaus.abels at hum.uit.no >
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
Announced at http://linguistlist.org/issues/15/15-1531.html


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

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 http://linguistlist.org/issues/16/16-1597.html), 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 
index. 

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

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 
http://kracht.humnet.ucla.edu/marcus/index.html).

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.

REFERENCES

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: 
Springer.

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. 

ABOUT THE REVIEWER

Klaus Abels is Associate Professor of Linguistics at the University of 
Tromsø. His research areas are syntax and semantics. 
[From http://uit.no/castl/2400/51 --Eds.]





-----------------------------------------------------------
LINGUIST List: Vol-16-2247