This festschrift honors the computer scientist Daniel Rosenkrantz. It is a bipartite book: Part 1 (chapters 1 to 10) comprises ten papers by Rosenkrantz and some of his colleagues, spanning from 1967 to 2008; Part 2 (chapters 11 to 18) presents eight papers by other computer scientists.

The unifying theme of the book is that, while Rosenkrantz’s work is mainly theoretical, it stems from practical information processing problems across several domains. The problem domains include concurrency control in distributed databases, a model for certain hierarchical versioned data, and efficient approximation of certain minimum cost networks. In each problem domain, by devising suitable abstractions in terms of graphs, Rosenkrantz and his co-authors resolve the problem into combinatorial optimization problems in nondeterministic polynomial time (NP). Other topics presented show the extensive range of Rosenkrantz’s research interests.

Part 1 begins with three papers (chapters 1 to 3, respectively): “Matrix equations and normal forms for context-free grammars,” “Attributed translations,” and “An analysis of several heuristics for the traveling salesman problem.” One highlight of Part 1 is the lucid and comprehensive treatment of concurrency control in chapter 4. The clear presentation of assumptions, along with the careful and thorough treatment of their consequences, make the book valuable for teaching purposes, especially since many textbooks dealing with this problem are unclear and inaccessible. Chapters 5 to 7 consist of the following three papers: “Consistency and serializability of concurrent database systems,” “An efficient method for representing and transmitting message patterns on multi-processor interconnection networks,” and “Representability of design objects by ancestor-controlled hierarchical specifications.” In work done with Harry Hunt, such as in chapters 8 and 9, PSPACE rather than NP is encountered. The abstractions reveal fundamental constraints to solutions that a more conventional and practical approach would almost certainly miss. Finally, Part 1 ends with chapter 10, “Efficient algorithms for segmentation of item-set time series.”

Part 2 begins with chapter 11, “Structure trees and subproblem independence.” Chapter 12 covers optimistic concurrency and replicated databases, and chapter 13 studies the concurrency concept of serializability; these papers expand on Rosenkrantz’s distributed database paper. However, replication is now a major research topic for semi-structured data communicated over the Web. A couple of the papers on mechanism design are an extension of Rosenkrantz’s approach of abstraction applied to information processing problems and human interaction. For example, in chapter 14, election systems use computational complexity as the cost to enforce desirable characteristics, such as minimizing fraud. Generally, mechanism design involves identifying costs and benefits to participants in some system of interaction, so that desirable behaviors among them can be largely maintained. Some of the papers consider problems related to the dynamic or online updating of structures associated with various information processing operations. Again, these papers represent an evolution of themes treated in Part 1, although in different domains. Chapters 15 to 18--“Fully dynamic bin packing,” “Online job admission,” “A survey of graph algorithms under extended streaming models of computation,” and “Interactions among human behavior, social networks and social infrastructures: a case study in computational epidemiology”--end Part 2.