TY - BOOK ID - 1667199 TI - Finite Model Theory and Its Applications AU - Grädel, Erich. AU - Kolaitis, Phokion G. AU - Libkin, Leonid. AU - Marx, Maarten. AU - Spencer, Joel. AU - Vardi, Moshe Y. AU - Venema, Yde. AU - Weinstein, Scott. PY - 2007 SN - 3540688048 3540004289 PB - Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, DB - UniCat KW - Finite model theory. KW - Computational complexity. KW - Constraint databases. KW - Databases KW - Complexity, Computational KW - Electronic data processing KW - Machine theory KW - Computer science KW - Model theory KW - Mathematics KW - Information theory. KW - Computer science. KW - Software engineering. KW - Logic design. KW - Database management. KW - Theory of Computation. KW - Mathematical Logic and Formal Languages. KW - Software Engineering. KW - Computation by Abstract Devices. KW - Logics and Meanings of Programs. KW - Database Management. KW - Data base management KW - Data services (Database management) KW - Database management services KW - DBMS (Computer science) KW - Generalized data management systems KW - Services, Database management KW - Systems, Database management KW - Systems, Generalized database management KW - Design, Logic KW - Design of logic systems KW - Digital electronics KW - Electronic circuit design KW - Logic circuits KW - Switching theory KW - Computer software engineering KW - Engineering KW - Informatics KW - Science KW - Communication theory KW - Communication KW - Cybernetics KW - Computers. KW - Mathematical logic. KW - Computer logic. KW - Computer science logic KW - Logic, Symbolic and mathematical KW - Algebra of logic KW - Logic, Universal KW - Mathematical logic KW - Symbolic and mathematical logic KW - Symbolic logic KW - Algebra, Abstract KW - Metamathematics KW - Set theory KW - Syllogism KW - Automatic computers KW - Automatic data processors KW - Computer hardware KW - Computing machines (Computers) KW - Electronic brains KW - Electronic calculating-machines KW - Electronic computers KW - Hardware, Computer KW - Computer systems KW - Calculators KW - Cyberspace UR - https://www.unicat.be/uniCat?func=search&query=sysid:1667199 AB - This book gives a broad overview of core topics of finite model theory: expressive power, descriptive complexity, and zero-one laws, together with selected applications to database theory and artificial intelligence, especially, constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, which emphasizes the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of, and hierarchies within, first order, second order, fixed point, and infinitary logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful technique for analyzing the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and tree-width, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research in finite model theory, and all readers will experience the excitement of a vibrant area of application of logic to computer science. ER -