ENGLISH

Descriptive Complexity

By Neil Immerman

Book information

Publisher
Springer
Year
1998
ISBN
0387986006, 9780387986005
Language
english
Format
DJVU
Filesize
2 MB (2232468 bytes)
Series
Graduate Texts in Computer Science
Pages
266\266
Topic
Mathematics Logic
Time added
2011-01-23 12:00:00

Description

A basic issue in computer science is the complexity of problems. Computational complexity measures how much time or memory is needed as a function of the input problem size. Descriptive complexity is concerned with problems which may be described in first-order logic. By virtue of the close relationship between logic and relational databases, it turns out that this subject has important applications to databases such as analyzing the queries computable in polynomial time, analyzing the parallel time needed to compute a query, and the analysis of non-deterministic classes. This book is written as a graduate text and so aims to provide a reasonably self-contained introduction to this subject. The author has provided numerous examples and exercises to further illustrate the ideas presented.

Similar books