Universitext

1 total work

The Classical Decision Problem

by E Boerger, E Bhorger, Yuri Gurevich, E Gradel, and Professor of Computer Science Department of Information Egon Borger

Published 31 December 1996

This treatment of the classical decision problem of mathematical logic and its role in modern computer science provides an analysis of the natural order of decidable and undecidable cases. Of particular interest is the complete classification of the solvable and unsolvable standard cases of the classical decision problem, the complexity analysis of the solvable cases, the extremely comprehensive treatment of the reduction method, and the model-theoretic analysis of solvable cases. Many simple proofs and exercises are included in the book.