| 000 | 02282nam a2200349 i 4500 | ||
|---|---|---|---|
| 001 | CR9781139028868 | ||
| 003 | UkCbUP | ||
| 005 | 20240906184219.0 | ||
| 006 | m|||||o||d|||||||| | ||
| 007 | cr|||||||||||| | ||
| 008 | 110221s2017||||enk o ||1 0|eng|d | ||
| 020 | _a9781139028868 (ebook) | ||
| 020 | _z9781107014527 (hardback) | ||
| 040 |
_aUkCbUP _beng _erda _cUkCbUP |
||
| 050 | 0 | 0 |
_aQA166 _b.G7545 2017 |
| 082 | 0 | 0 |
_a511/.5 _223 |
| 100 | 1 |
_aGrohe, M. _q(Martin), _eauthor. |
|
| 245 | 1 | 0 |
_aDescriptive complexity, canonisation, and definable graph structure theory / _cMartin Grohe. |
| 264 | 1 |
_aCambridge : _bCambridge University Press, _c2017. |
|
| 300 |
_a1 online resource (ix, 543 pages) : _bdigital, PDF file(s). |
||
| 336 |
_atext _btxt _2rdacontent |
||
| 337 |
_acomputer _bc _2rdamedia |
||
| 338 |
_aonline resource _bcr _2rdacarrier |
||
| 490 | 1 |
_aLecture notes in logic ; _v47 |
|
| 500 | _aTitle from publisher's bibliographic system (viewed on 30 Aug 2017). | ||
| 520 | _aDescriptive complexity theory establishes a connection between the computational complexity of algorithmic problems (the computational resources required to solve the problems) and their descriptive complexity (the language resources required to describe the problems). This groundbreaking book approaches descriptive complexity from the angle of modern structural graph theory, specifically graph minor theory. It develops a 'definable structure theory' concerned with the logical definability of graph theoretic concepts such as tree decompositions and embeddings. The first part starts with an introduction to the background, from logic, complexity, and graph theory, and develops the theory up to first applications in descriptive complexity theory and graph isomorphism testing. It may serve as the basis for a graduate-level course. The second part is more advanced and mainly devoted to the proof of a single, previously unpublished theorem: properties of graphs with excluded minors are decidable in polynomial time if, and only if, they are definable in fixed-point logic with counting. | ||
| 650 | 0 | _aGraph theory. | |
| 776 | 0 | 8 |
_iPrint version: _z9781107014527 |
| 830 | 0 |
_aLecture notes in logic ; _v47. |
|
| 856 | 4 | 0 | _uhttps://doi.org/10.1017/9781139028868 |
| 942 |
_2ddc _cEB |
||
| 999 |
_c9848 _d9848 |
||