Date: Fri, 15 Jul 2005 18:04:39 +0200 From: Klaus Abels <klaus.abels@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
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 nontrivial 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/161597.html), books in the Studies in Generative Grammar series do not appear to be seriously proofread. The text contains an annoying number of meaningdistorting 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 overambitious: 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 backcover). 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.
