Droste M., Kuich W., Vogler H.
Handbook of weighted automata.
Springer Publishing Company, Incorporated, 2009.
ACM categories: F.1.1 Automata; A.2 Reference

The first thing that struck me about this new handbook was its weight. If some of the more distant connections to the topic of weighted automata had been removed, it would have been much handier. This is not to say that the contributions are not good—most of them are excellent tutorials, by very knowledgeable experts—but that the editors have tried to cover too much.

I found Mohri's chapter on algorithms for weighted transducers the most satisfying. It gets straight to the heart of the matter—what changes are to be made to the theory we usually learn, when weights are added to the finite automata and transducers? The background required is no more than undergraduate level. This chapter, slightly fleshed out, would have been a good introduction to the field. Instead, the first section, on fundamentals, has two dense chapters on semirings, formal power series, and fixed points, which will turn off most computer science undergraduates. Of course, this information has to be available in a handbook of this kind, but I would have preferred it to come later.

The next section, “Automata,” is the core of the book. It begins with a chapter by Ésik and Kuich that deals with automata on finite and infinite words. This makes it clear how the weighted approach depends on computation on transition matrices. The long chapter by Sakarovitch that follows turns out to be two chapters of his recently published book [1], rewritten to include a commentary on Ésik and Kuich about automata on finite words. While I like the idea of a commentary (and Sakarovitch does make some thought-provoking points), I do not see why both chapters had to cover the same material, adding to the book's size. Droste and Gastin's chapter on logics is really about the technical challenges faced when adapting the Büchi-Elgot-Trakhtenbrot theorem on words to the weighted case. I find it philosophically unsatisfying to have a logic where the set of semantic values is a semiring. The chapter by Rahonis on fuzzy logics, in the later section “Applications,” makes more sense in conjunction with this chapter. (Another “Applications” chapter is on probabilistic transition systems.) Proponents of many-valued logics, such as Zadeh, have carefully argued the use of the many values. By contrast, the authors of this chapter end with a cavalier “Open problem 4: Find applications.”

So, the section on automata is about how the standard theorems on regular languages are extended to the weighted case. The basics of these were covered in Eilenberg's treatise [2], more than 30 years ago. Later monographs by Salomaa et al. [3,4] and by Berstel and Reutenauer [5] further developed the notion of formal power series, which are weighted generalizations of languages.

The next section, “Discrete Structures,” follows the same style, providing an update on how a variety of structures, such as trees, Mazurkiewicz traces, series-parallel posets and pictures, as well as richer classes of word languages generated by context-free grammars and Lindenmayer systems, can be dealt with when weights are introduced.

I have already referred to the final section, “Applications.” I must add that the last chapter, by Knight and May, on natural language processing, is the most enjoyable of the book. I had always thought that translation was the hard part of this area; I was surprised to find out how much work has to be done—and is being done—on the seemingly easy problem of transliteration, and the role weighted transducers play in it.

In summary, this is a book to keep on a library shelf, to be used as a reference by the theoretically inclined when needed.

[1] Sakarovitch, J. Elements of automata theory. Cambridge University Press, New York, NY, 2009.
[2] Eilenberg, S. Automata, languages, and machines. Academic Press, Orlando, FL, 1974.
[3] Salomaa, A.; Soittola, M. Automata: theoretic aspects of formal power series. Springer-Verlag, New York, NY, 1978.
[4] Kuich, W.; Salomaa, A. Semirings, automata, languages. Springer-Verlag, London, UK, 1986.
[5] Berstel, J.; Reutenauer, C. Rational series and their languages. Springer-Verlag, Berlin, Germany, 1988.