000 03007nam a22006135i 4500
001 978-3-662-54314-6
003 DE-He213
005 20240730194144.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
_9155958
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.
_99832
650 0 _aSoftware engineering.
_94138
650 0 _aMachine theory.
_9155959
650 0 _aCompilers (Computer programs).
_93350
650 0 _aAlgorithms.
_93390
650 0 _aComputer programming.
_94169
650 1 4 _aComputer Science Logic and Foundations of Programming.
_942203
650 2 4 _aSoftware Engineering.
_94138
650 2 4 _aFormal Languages and Automata Theory.
_9155960
650 2 4 _aCompilers and Interpreters.
_931853
650 2 4 _aAlgorithms.
_93390
650 2 4 _aProgramming Techniques.
_9155961
710 2 _aSpringerLink (Online service)
_9155962
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
_9155963
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 _cELN
999 _c95056
_d95056