Cover Image
Read Now

Small Dynamic Complexity Classes An Investigation into Dynamic Descriptive Complexity

"Small Dynamic Complexity Classes" was awarded the E.W. Beth Dissertation Prize 2016 for outstanding dissertations in the fields of logic, language, and information. The thesis studies the foundations of query re-evaluation after modifying a database. It explores the structure of small dyn...

Full description

Bibliographic Details
Main Author: Zeume, Thomas
Format: eBook
Language:English
Published: Berlin, Heidelberg Springer Berlin Heidelberg 2017, 2017
Edition:1st ed. 2017
Series:Theoretical Computer Science and General Issues
Subjects:
Compilers (computer Programs)
Computer Science Logic And Foundations Of Programming
Compilers And Interpreters
Software Engineering
Programming Techniques
Computer Science
Computer Programming
Algorithms
Formal Languages And Automata Theory
Machine Theory
Online Access:
Collection: Springer eBooks 2005- - Collection details see MPG.ReNa
Description
Summary:"Small Dynamic Complexity Classes" was awarded the E.W. Beth Dissertation Prize 2016 for outstanding dissertations in the fields of logic, language, and information. The thesis studies the foundations of query re-evaluation after modifying a database. It explores the structure of small dynamic descriptive complexity classes and provides new methods for proving lower bounds in this dynamic context. One of the contributions to the former aspect helped to confirm the conjecture by Patnaik and Immerman (1997) that reachability can be maintained by first-order update formulas
Physical Description:VIII, 149 p. 17 illus online resource
ISBN:9783662543146

Similar Items