Search Images Maps Play YouTube News Gmail Drive More »
My library | Help | Advanced Book Search | Web History | Sign in

Books

Finite Model Theory.

Front Cover
0 Reviews
Springer, 1999 - Mathematics - 360 pages

The 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 logics that are important in this context include fixed-point logics, transitive closure logics, 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 descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text.

  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Related books

Foundations of Databases
Foundations of Databases
Serge Abiteboul,Richard Hull,Victor Vianu
Snippet view - 1995
ISILC Logic Conference: proceedings of the International Summer Institute ...
ISILC Logic Conference: proceedings of the International Summer Institute ...
Gert Heinz Müller,Arnold Oberschelp,Karl Potthoff
Snippet view - 1975
Computational complexity
Computational complexity
Christos H. Papadimitriou
Snippet view - 1994
All related books »

Selected pages

Contents

II
1
III
13
V
15
VI
20
VII
26
VIII
30
IX
37
XI
40
XLI
162
XLII
165
XLIV
177
XLV
191
XLVI
198
XLVII
205
XLVIII
207
XLIX
210

XII
46
XIII
49
XIV
54
XV
56
XVI
58
XVII
62
XVIII
71
XX
74
XXI
77
XXII
82
XXIII
84
XXIV
88
XXV
95
XXVII
99
XXVIII
105
XXX
108
XXXI
111
XXXII
114
XXXIII
119
XXXIV
120
XXXV
124
XXXVI
127
XXXVII
129
XXXVIII
133
XXXIX
147
XL
151
L
217
LI
220
LII
221
LIII
224
LIV
229
LV
235
LVI
239
LVIII
245
LIX
250
LX
253
LXI
263
LXII
268
LXIII
275
LXV
280
LXVI
287
LXVII
288
LXVIII
295
LXIX
307
LXX
308
LXXI
314
LXXII
320
LXXIII
330
LXXIV
339
LXXV
349
Copyright

Other editions - View all

Finite Model Theory
Finite Model Theory
Heinz-Dieter Ebbinghaus,Jr̲g Flum,Jörg Flum
Limited preview - 2005
Finite model theory
Finite model theory
Heinz-Dieter Ebbinghaus,Jörg Flum
Snippet view - 1995
Finite Model Theory
Finite Model Theory
Heinz-Dieter Ebbinghaus,Jörg Flum
No preview available - 2005

Common terms and phrases

accepts arity assume atomic formulas axiomatizable axioms binary relation cardinality class of finite class of ordered class of structures clause complexity class complexity theory configuration contains Corollary corresponding DATALOG definition denote deterministic digraph duplicator wins effectively strongly captures example Exercise existential expressive power finite model finite structures first-order formula first-order logic first-order sentence fixed-point logic FO(DTC FO(LFP FO(LFP)-formula following are equivalent free variables given hence I-DATALOG input tapes intentional symbols isomorphism type Lemma length lexicographic ordering LFP operator log space-bounded LOGSPACE logspace reductions model theory monotone natural numbers nontrivial obtained oracle machine oracle tapes ordered structures partial isomorphism polynomial positive Pow(A preceding proof Proposition PSPACE quantifier rank quantifier-free r-structures regular expressions relation symbol satisfies second-order logic sequence spoiler Str[r strongly captures PTIME subformula subset Suppose Theorem totally defined transitive closure tuples Turing machine unary vocabulary

Popular passages

Page 344 - Society, 1989. [Kol90] Ph. G. Kolaitis. Implicit definability on finite structures and unambiguous computations. In Proc. 5th IEEE Symp. on Logic in Computer Science, pages 168-180, 1990.‎
Appears in 6 books from 1990-1999
Page 344 - Computation, 83:121-139, 1989. [Imm82] N. Immerman. Upper and lower bounds for first-order expressibility. Journal of Computer and System Sciences, 25:76-98, 1982.‎
Appears in 17 books from 1986-2007
Page 346 - L. Pacholski and W. Szwast, The 0-1 law fails for the class of existential second-order Godel sentences with equality, Proc.‎
Appears in 8 books from 1990-1999
Page 344 - December 1977. [Imm88] N. Immerman. Nondeterministic space is closed under complement. SIAM Journal ' on Computing, 17:935-938, 1988.‎
Appears in 11 books from 1991-2007
Page 345 - Ph. G. Kolaitis and MY Vardi. Fixpoint logic vs. infinitary logic in finite-model theory. In Proc. 7th IEEE Symp. on Logic in Computer Science, pages 46-57, 1992.‎
Appears in 10 books from 1931-2007

References to this book

From other books

Handbook of Formal Languages: Beyond Words
Handbook of Formal Languages: Beyond Words
Grzegorz Rozenberg,Arto Salomaa
No preview available - 1997
Parameterized complexity theory
Parameterized complexity theory
Jörg Flum,Martin. Grohe
No preview available - 2006
All Book Search results »

From Google Scholar

Complexity and Expressive Power of Logic Programming
EVGENY DANTSIN, THOMAS EITER, GEORG GOTTLOB, ANDREI VORONKOV - 2001 - ACM Computing Surveys
Linear Time Solvable Optimization Problems on Graphs of Bounded ...
B Courcelle, JA Makowsky, U Rotics - 2000 - Theory of Computing Systems
Relational Expressive Power of Constraint Query Languages
MICHAEL BENEDIKT, GUOZHU DONG, LEONID LIBKIN, LIMSOON WONG - 1998 - Journal of the ACM
Automatic Structures
Achim Blumensath, Erich Grädel, RWTH Aachen
All Scholar search results »

References from web pages

JSTOR: Finite Model Theory.
Finite model theory. Perspectives in mathematical logic. Springer, Berlin, Heidelberg, New York, etc., 1995, xv + 327 pp. Finite model theory is a ...
links.jstor.org/ sici?sici=0022-4812(199609)61%3A3%3C1049%3AFMT%3E2.0.CO%3B2-0

3 Finite Model Theory and Descriptive Complexity
finite model theory can be extended to suitable domains of infinite ... One of the central issues in finite model theory is the relationship between ...
www.logic.rwth-aachen.de/ pub/ graedel/ FMTbook-Chapter3.pdf

A Finite Model Theory for Biological Hypotheses
ing techniques from finite model theory and present results. on decidability, satisfiability, discoverability, and inflation-. ary/deflationary operators. ...
doi.ieeecomputersociety.org/ 10.1109/ CSB.2004.1332518

CIDEC Library: Ebbinghaus * Finite Model Theory
Finite model theory has its origin in classical model theory, but owes its systematic development to research from complexity theory. ...
cs.ioc.ee/ yik/ lib/ 1/ Ebbinghaus1.html

Finite Model Theory on Tame Classes of Structures
The early days of finite model theory saw a variety of results ... Finite model theory is the study of the expressive power of various logics—such ...
www.springerlink.com/ index/ 0175103238141615.pdf

Zentralblatt MATH Database 1931 – 2008 0841.03014
Finite model theory is a young and rapidly developing area of research which has its ... Finite model theory uses methods from finite combinatorics. ...
zmath.impa.br/ cgi-bin/ zmen/ ZMATH/ en/ zmath.html?first=1& maxdocs=3& type=pdf& an=0841.03014& format=complete

Math 512: Finite Model Theory
The course will address basic issues in finite model theory: Ehrenfreuht-Fraisse games, descriptive complexity theory, $0-1$-laws. ...
www.math.uic.edu/ ~jbaldwin/ fmt512.html

Preservation Theorems in Finite Model Theory - Rosen, Weinstein ...
We develop various aspects of the finite model theory of L k and L k We establish the optimality of normal forms for L k over the class of finite structures ...
citeseer.ist.psu.edu/ 74130.html

avaxhome -> ebooks -> Science -> Mathematics -> Finite Model Theory
Finite Model Theory. Posted By: ertugrul ergun | Date: 05 Jun 2007 05:40 | Comments: 0. Heinz-Dieter Ebbinghaus, Jörg Flum, "Finite Model Theory" ...
avaxsphere.com/ ebooks/ science_books/ math/ FiniteModelTheory.html

FINITE MODEL THEORY (Perspectives in Mathematical Logic) By Heinz ...
FINITE MODEL THEORY (Perspectives in Mathematical Logic) By Heinz-Dieter Ebbinghaus and Jorg Flum: 327 pp., DM. 148.–, ISBN 3 540 60149 X (Springer, 1995). ...
journals.cambridge.org/ abstract_S0024609396222416

About the author (1999)

Prof. Jvrg Flum, Abteilung f]r Mathematische Logik, Albert-Ludwigs-Universitdt Freiburg, Germany, http: //logik.mathematik.uni-freiburg.de/personen/Flum.html Prof. Martin Grohe, Institut f]r Informatik, Humboldt-Universitdt zu Berlin, Germany, http: //www.informatik.hu-berlin.de/~grohe/ The authors are very well qualified to write this book. In addition to their strong backgrounds in complexity, algorithms, etc., they have contributed a number of specific key results in parameterized complexity (e.g., http: //epubs.siam.org/sam-bin/dbq/article/42720). Jvrg Flum has coauthored two other Springer monographs: (i) "Mathematical Logic," Undergraduate Texts in Mathematics, 0-387-94258-0, 3rd printing since 1994, over 4000 copies sold, Heinz-Dieter Ebbinghaus, Jvrg Flum, Wolfgang Thomas, http: //www.springer.com/0-387-94258-0. (ii) "Finite Model Theory," Springer Monographs in Mathematics (was in series Perspectives in Mathematical Logic), printed in soft- and hardback, 1995, 2nd ed. in 1999, 2nd corr. print in 2006, Heinz-Dieter Ebbinghaus, Jvrg Flum, 3-540-28787-6, http: //www.springer.com/3-540-28787-6. In addition, Jvrg Flum coauthored the following LNM title: Vol. 769, "Topological Model Theory, 1980, 3-540-09732-5, Jvrg Flum, Martin Ziegler. And he coedited the following LNCS title: Vol. 1683, CSL 1999 conf. proc., Jvrg Flum, Mario Rodriguez-Artalejo, 1999, 3-540-66536-6. Prof. Martin Grohe has authored over 50 articles for refereed theoretical computer science journals and conference proceedings (http: //www.informatik.uni-trier.de/~ley/db/indices/a-tree/g/Grohe: Martin.html) in the areas of logic, complexity, algorithms, etc.

Bibliographic information

QR code for Finite Model Theory.
TitleFinite Model Theory.
Perspectives in mathematical logic, ISSN 0172-6641
Springer monographs in mathematics
AuthorsH.-D. Ebbinghaus, J. Flum
Edition2, illustrated
PublisherSpringer, 1999
ISBN3540657584, 9783540657583
Length360 pages
Subjects › 

Mathematics / Logic
  
Export CitationBiBTeX EndNote RefMan