Cantitate/Preț
Produs
Total produse
Vezi coșul
Finite Model Theory: Second Edition de Heinz-Dieter Ebbinghaus

Finite Model Theory: Second Edition: Springer Monographs in Mathematics

Autor Heinz-Dieter Ebbinghaus, Jörg Flum
en Limba Engleză Hardback – 6 oct 2005

Remarcăm în această a doua ediție a volumului Finite Model Theory o abordare riguroasă a interdependenței dintre logica matematică, informatica teoretică și combinatorică. Spre deosebire de model teoria clasică, ce operează predilect în domeniul infinitului, lucrarea de față se concentrează pe semantica limbajelor formalizate aplicate structurilor finite, un domeniu a cărui dezvoltare a fost accelerată de întrebările fundamentale din teoria bazelor de date și complexitatea computațională.

Autorii Heinz-Dieter Ebbinghaus și Jörg Flum propun o structură progresivă, începând cu instrumente fundamentale precum jocurile Ehrenfeucht-Fraïssé, esențiale pentru a demonstra inexpresivitatea anumitor proprietăți în logica de ordinul întâi. Progresia narativă a volumului ne conduce prin analiza legilor 0-1 și a satisfiabilității, culminând cu o examinare detaliată a complexității descriptive și a programelor logice. Această ediție extinsă rafinează conceptele prezentate anterior, menținând un echilibru între fundamentul teoretic și aplicațiile practice în optimizare și PTIME.

Considerăm că această lucrare acoperă aceeași arie tematică precum Elements of Finite Model Theory de Leonid Libkin, însă Heinz-Dieter Ebbinghaus și Jörg Flum adoptă o perspectivă ancorată mai profund în tradiția logicii matematice pure. În timp ce Libkin pune accent pe aplicațiile imediate în informatică, volumul de față servește ca o punte teoretică între logica de ordinul întâi, explorată de autori în Mathematical Logic, și sistemele de axiomatizare tratate în Einführung in die Mengenlehre. Este o resursă indispensabilă pentru cercetătorii care doresc să înțeleagă de ce instrumente clasice, precum teorema de compactitate, devin inoperante în universul finit și ce mecanisme logice le pot înlocui.

Citește tot Restrânge

Din seria Springer Monographs in Mathematics

Preț: 107316 lei

Preț vechi: 130873 lei
-18%

Puncte Express: 1610

Carte tipărită la comandă

Livrare economică 20 mai-03 iunie

 Adaugă în coș

Wish list
Gift list
Am citit!
Adaugă în listă

Specificații

ISBN-13: 9783540287872
ISBN-10: 3540287876
Pagini: 374
Ilustrații: XI, 360 p.
Dimensiuni: 155 x 235 x 27 mm
Greutate: 0.67 kg
Ediția:2nd ed. 1999. 2nd printing 2005
Editura: Springer Berlin, Heidelberg
Colecția Springer
Seria Springer Monographs in Mathematics

Locul publicării:Berlin, Heidelberg, Germany

Public țintă

Research

De ce să citești această carte

Recomandăm această monografie cercetătorilor și studenților la masterat care studiază intersecția dintre matematică și informatică. Cititorul câștigă o înțelegere profundă a modului în care logica poate clasifica problemele computaționale în funcție de complexitatea lor descriptivă. Este un text de referință care explică riguros de ce modelele finite necesită un aparat logic distinct de cel al structurilor infinite, oferind instrumente matematice precise pentru analiza bazelor de date.

Descriere scurtă

Finite model theory, the model theory of finite structures, has roots in clas­ sical model theory; however, its systematic development was strongly influ­ enced by research and questions of complexity theory and of database theory. Model theory or the theory of models, as it was first named by Tarski in 1954, may be considered as the part of the semantics of formalized languages that is concerned with the interplay between the syntactic structure of an axiom system on the one hand and (algebraic, settheoretic, . . . ) properties of its models on the other hand. As it turned out, first-order language (we mostly speak of first-order logic) became the most prominent language in this respect, the reason being that it obeys some fundamental principles such as the compactness theorem and the completeness theorem. These principles are valuable modeltheoretic tools and, at the same time, reflect the expressive weakness of first-order logic. This weakness is the breeding ground for the freedomwhich modeltheoretic methods rest upon. By compactness, any first-order axiom system either has only finite models of limited cardinality or has infinite models. The first case is trivial because finitely many finite structures can explicitly be described by a first-order sentence. As model theory usually considers all models of an axiom system, modeltheorists were thus led to the second case, that is, to infinite structures. In fact, classical model theory of first-order logic and its generalizations to stronger languages live in the realm of the infinite.

Cuprins

Preliminaries.- The Ehrenfeucht-Fraïssé Method.- More on Games.- 0-1 Laws.- Satisfiability in the Finite.- Finite Automata and Logic: A Microcosm of Finite Model Theory.- Descriptive Complexity Theory.- Logics with Fixed-Point Operators.- Logic Programs.- Optimization Problems.- Logics for PTIME.- Quantifiers and Logical Reductions.

Caracteristici

Explores connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds Includes important logics: fixed-point logics, transitive closure logics, and also certain infinitary languages Additional topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems The new Second Edition is thoroughly revised and enlarged Includes supplementary material: sn.pub/extras