Selected book contributions

The Classical Decision Problem book

Egon Börger, Erich Grädel, Yuri Gurevich
``Classical Decison Problem''
Springer Verlag, Perspectives in Mathematical Logic, 1997
Second printing, Springer Verlag, 2001
Contents and Introduction.
Review in Journal of Logic, Language and Information 8(4) (1999), 478--481.
Review in ACM SIGACT News 35:1 (March 2004), 4--7.

The classical decision problem is (in its modern meaning) the problem of classifying fragments of first-order logic with respect to the decidability and complexity of the satisfiability problem as well as the satisfiability problem over finite domains. The results and methods employed are used in logic, computer science and artifical intelligence.
     The book gives the most complete and comprehensive treatment of the classical decision problem to date, and includes an annotated biblography of 549 items. Much of the material is published for the first time in book form; this includes the classifiability theory, the classification of the so-called standard fragments, and the analysis of the reduction method. Many proofs have been simplified and there are many new results and proofs.

Books with multiple contributions of Yuri Gurevich


[2004]

Yuri Gurevich and guest authors
"Logic in Computer Science"
chapter (pages 95--311) in book

Current Trends in Theoretical Computer Science:
The Challenge of the New Century

Volume 2: Formal Models and Semantics
eds. G. Paun, G. Rozenberg and A. Salomaa
World Scientific, 2004

The chapter consists of articles published in the column on Logic in Computer Science in the Bulletin of European Association for Theoretical Computer Science from the October 2000 issue till the October 2003 issue.

[2001]

Yuri Gurevich and guest authors
"Logic in Computer Science"
chapter (pages 233--436) in book

Current Trends in Theoretical Computer Science:
Entering the 21st Century

eds. G. Paun, G. Rozenberg and A. Salomaa
World Scientific, 2001

With one exception, the chapter consists of articles published in the column on Logic in Computer Science in the Bulletin of European Association for Theoretical Computer Science from the October 1992 issue till the February 2000 issue. The exception is the banquet talk published in the Bulletin outside the column.

[1995]

Specification and Validation Methods
ed. E. Boerger, Oxford University Press, 1995

[1993]

Yuri Gurevich and guest authors
"Logic in Computer Science"
chapter (pages 223--394) in book

Current Trends in Theoretical Computer Science:
Essays and Tutorials

eds. G. Rozenberg and A. Salomaa
World Scientific, 1993

With one exception, the chapter consists of the articles published in the column on Logic in Computer Science in the Bulletin of European Association for Theoretical Computer Science from the inception of the column in 1988 till the June 1992 issue. The exception is an updated version of the evolving algebra tutorial published in the Bulletin outside the column.