Finite model theory

Mostrar otras versiones (1)

This book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logic that is important in this context include fixed-point logic, transitive closur...

Descripción completa

Detalles Bibliográficos
Autores principales: Ebbinghaus, Heinz-Dieter, Flum, Jörg
Lenguaje:eng
Publicado: Springer 2006
Materias:
Mathematical Physics and Mathematics
Acceso en línea:https://dx.doi.org/10.1007/3-540-28788-4
http://cds.cern.ch/record/913322
_version_ 1780908945123049472
author Ebbinghaus, Heinz-Dieter
Flum, Jörg
author_facet Ebbinghaus, Heinz-Dieter
Flum, Jörg
author_sort Ebbinghaus, Heinz-Dieter
collection CERN
description This book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logic that is important in this context include fixed-point logic, transitive closure logic, and also certain infinitary languages - their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descr
id cern-913322
institution Organización Europea para la Investigación Nuclear
language eng
publishDate 2006
publisher Springer
record_format invenio
spelling cern-9133222021-04-22T02:16:33Zdoi:10.1007/3-540-28788-4http://cds.cern.ch/record/913322engEbbinghaus, Heinz-DieterFlum, JörgFinite model theoryMathematical Physics and MathematicsThis book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logic that is important in this context include fixed-point logic, transitive closure logic, and also certain infinitary languages - their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descrSpringeroai:cds.cern.ch:9133222006
spellingShingle Mathematical Physics and Mathematics
Ebbinghaus, Heinz-Dieter
Flum, Jörg
Finite model theory
title Finite model theory
title_full Finite model theory
title_fullStr Finite model theory
title_full_unstemmed Finite model theory
title_short Finite model theory
title_sort finite model theory
topic Mathematical Physics and Mathematics
url https://dx.doi.org/10.1007/3-540-28788-4
http://cds.cern.ch/record/913322
work_keys_str_mv AT ebbinghausheinzdieter finitemodeltheory
AT flumjorg finitemodeltheory

Ejemplares similares