xiv Preface It is hoped that this book will facilitate communication between the various groups of people who are actively involved in the computer revolution,and between that group,and those who,for the time being,are observers only. David Harel Pittsburgh,Pennsylvania February,1987 New to the Second Edition See,this is new;but it has already been ECCLESIASTES 1:10 The first edition of this book was intended to be read from beginning to end,and could be used as supplementary reading in a number of courses.Teaching a course based exclusively on it was possible,but would have required the instructor to prepare exercises and add examples and more detail in certain places.The present edition contains numerous exercises,as well as solutions to about a third of them. The solved exercises can thus be used to supplement the text.Three chapters have not been supplied with exercises.Chapter 1 is an introduction,the bulk of Chapter 3 is really just a brief survey of several programming languages,and Chapter 12 is a nontechnical account of some topics in artificial intelligence.2 In a sense,the three are not integral parts of the topic of the book-algorithmics-and hence in teaching a course based on the book these should probably be assigned as homework reading. The text itself remains largely without change,except for a new section in Chapter 11 describing the recent topics of interactive proofs and zero-knowledge. The reader may wonder why a more extensive revision of the text was not called for.Have computer scientists been idle during the five years since the first edition was written?Rather than taking this as a criticism of the field,I think that it shows that the topics selected for inclusion in the book are really of fundamental nature, so that no significant changes had to be made.The issues discussed herein are thus probably basic and lasting.Maybe the term"classical"is most fitting David Harel Rehovot,Israel May,1991 New to the Third Edition they three iere of one measure EZEKIEL 40:10 This time around,a significant revision was carried out.There are several important changes in this edition of the book,compared to the first and second editions, including two brand new chapters,new sections,and more 2 Again,see the section below,"New to the third edition."as some of these chapter numbers have changed.P1: GIG PE002-FM PE002-Harel PE002-Harel-FM-v1.cls March 19, 2004 19:35 xiv Preface It is hoped that this book will facilitate communication between the various groups of people who are actively involved in the computer revolution, and between that group, and those who, for the time being, are observers only. David Harel Pittsburgh, Pennsylvania February, 1987 ■ New to the Second Edition See, this is new; but it has already been ECCLESIASTES 1: 10 The first edition of this book was intended to be read from beginning to end, and could be used as supplementary reading in a number of courses. Teaching a course based exclusively on it was possible, but would have required the instructor to prepare exercises and add examples and more detail in certain places. The present edition contains numerous exercises, as well as solutions to about a third of them. The solved exercises can thus be used to supplement the text. Three chapters have not been supplied with exercises. Chapter 1 is an introduction, the bulk of Chapter 3 is really just a brief survey of several programming languages, and Chapter 12 is a nontechnical account of some topics in artificial intelligence.2 In a sense, the three are not integral parts of the topic of the book—algorithmics—and hence in teaching a course based on the book these should probably be assigned as homework reading. The text itself remains largely without change, except for a new section in Chapter 11 describing the recent topics of interactive proofs and zero-knowledge. The reader may wonder why a more extensive revision of the text was not called for. Have computer scientists been idle during the five years since the first edition was written? Rather than taking this as a criticism of the field, I think that it shows that the topics selected for inclusion in the book are really of fundamental nature, so that no significant changes had to be made. The issues discussed herein are thus probably basic and lasting. Maybe the term “classical” is most fitting. David Harel Rehovot, Israel May, 1991 ■ New to the Third Edition they three were of one measure EZEKIEL 40: 10 This time around, a significant revision was carried out. There are several important changes in this edition of the book, compared to the first and second editions, including two brand new chapters, new sections, and more. 2 Again, see the section below, “New to the third edition,” as some of these chapter numbers have changed