Cambridge: Cambridge University Press. ix, 251 p. £ 30.00, $ 44.95 (1997).
This book gives an extremly broad account of computability, it embraces not only the general theory (halting problem, Turing computability, Turing and many-one reducibilities, degrees, immune and simple sets, Recursion Theorem, primitive recursion, oracle machines, recursive ennumerability, index sets, priority method, recursive isomorphisms, creative sets, cylinders, abstract complexity theory), but also the theory of finite functions and relations initiated by Post, the theory of regular languages from a number of points of view (finite automata, regular expressions, logical expressions, monoids, aperiodicity, varieties), and the theory of other families of languages (linear, context-free languages, ambiguity, rational cones, formal power series). These are addressed both from the classical perspective (grammars and automata) and from more modern perspectives (rational cones, logical descriptions). In large parts, the book is written for those making their way to the frontier of research. Proofs are given more fully than usual. Various exercises are included.