000 02910nam a22006135i 4500
001 978-3-662-54314-6
003 DE-He213
005 20240423125905.0
007 cr nn 008mamaa
008 170217s2017 gw | s |||| 0|eng d
020 _a9783662543146
_9978-3-662-54314-6
024 7 _a10.1007/978-3-662-54314-6
_2doi
050 4 _aQA75.5-76.95
072 7 _aUYA
_2bicssc
072 7 _aCOM014000
_2bisacsh
072 7 _aUYA
_2thema
082 0 4 _a004.0151
_223
100 1 _aZeume, Thomas.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
245 1 0 _aSmall Dynamic Complexity Classes
_h[electronic resource] :
_bAn Investigation into Dynamic Descriptive Complexity /
_cby Thomas Zeume.
250 _a1st ed. 2017.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2017.
300 _aVIII, 149 p. 17 illus.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v10110
505 0 _aDynamic Complexity: Definitions and Examples -- Relating Small Dynamic Complexity Classes -- Lower Bounds for Dynamic Complexity Classes. .
520 _a"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.
650 0 _aComputer science.
650 0 _aSoftware engineering.
650 0 _aMachine theory.
650 0 _aCompilers (Computer programs).
650 0 _aAlgorithms.
650 0 _aComputer programming.
650 1 4 _aComputer Science Logic and Foundations of Programming.
650 2 4 _aSoftware Engineering.
650 2 4 _aFormal Languages and Automata Theory.
650 2 4 _aCompilers and Interpreters.
650 2 4 _aAlgorithms.
650 2 4 _aProgramming Techniques.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783662543139
776 0 8 _iPrinted edition:
_z9783662543153
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v10110
856 4 0 _uhttps://doi.org/10.1007/978-3-662-54314-6
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cSPRINGER
999 _c182787
_d182787