Report file quality
lgli/Immerman - Descriptive Complexity.pdf
Descriptive Complexity 🔍
by Neil Immerman Springer Science+Business Media, LLC, Springer Nature (Textbooks & Major Reference Works), New York, NY, 2012
English [en] · PDF · 23.1MB · 2012 · 📘 Book (non-fiction) · 🚀/lgli/zlib · Save
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 databses, it turns out that this subject has important applications to databases such as analysing the queries computable in polynomial time, analysing the parallel time needed to compute a query, and the analysis of nondeterministic 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.
Erscheinungsdatum: 30.09.2012
Alternative filename
zlib/no-category/Immerman/Descriptive Complexity_2818426.pdf
Alternative publisher
Springer New York
Alternative publisher
Springer Nature
Alternative edition
Graduate Texts in Computer Science, Graduate texts in computer science, New York, NY, United States, 1999
Alternative edition
Graduate texts in computer science (Springer-Verlag New York Inc.), 1st ed. 1999, New York, 1999
Alternative edition
United States, United States of America
Alternative edition
1, 20121206
metadata comments
类型: 图书
metadata comments
丛书名: Graduate Texts in Computer Science
metadata comments
出版日期: 1999
metadata comments
出版社: springer
metadata comments
Online full text is restricted to subscribers.
Also available in print.
Mode of access: World Wide Web.
Alternative description
By virtue of the close relationship between logic and relational databases, it turns out that complexity has important applications to databases such as analyzing the parallel time needed to compute a query, and the analysis of nondeterministic classes. This book is a relatively self-contained introduction to the subject, which includes the necessary background material, as well as numerous examples and exercises.
Alternative description
Introduction
Background in Logic
Background in Complexity
First-Order Reductions
Inductive Definitions
Parallelism
Ehrenfeucht-Fraisse Games
Second-Order Logic and Fagin's Theorem
Second-Order Lower Bounds
Complementation and Transitive Closure
Polynomial Space
Uniformity and Precomputation
The Role of Ordering
Lower Bounds
Applications
Conclusions and Future Directions.
date open sourced
2018-04-25
Read more…

🚀 Fast downloads

Become a member to support the long-term preservation of books, papers, and more. To show our gratitude for your support, you get fast downloads. ❤️

🐢 Slow downloads

From trusted partners. More information in the FAQ. (might require browser verification — unlimited downloads!)

All download options have the same file, and should be safe to use. That said, always be cautious when downloading files from the internet, especially from sites external to Anna’s Archive. For example, be sure to keep your devices updated.
show external downloads
  • For large files, we recommend using a download manager to prevent interruptions.
    Recommended download managers: Motrix
  • You will need an ebook or PDF reader to open the file, depending on the file format.
    Recommended ebook readers: Anna’s Archive online viewer, ReadEra, and Calibre
  • Use online tools to convert between formats.
    Recommended conversion tools: CloudConvert and PrintFriendly
  • You can send both PDF and EPUB files to your Kindle or Kobo eReader.
    Recommended tools: Amazon‘s “Send to Kindle” and djazz‘s “Send to Kobo/Kindle”
  • Support authors and libraries
    ✍️ If you like this and can afford it, consider buying the original, or supporting the authors directly.
    📚 If this is available at your local library, consider borrowing it for free there.