Finite Model Theory and Its Applications
暫譯: 有限模型理論及其應用

有限模型理論在此理解為一個數學邏輯的領域，與計算機科學的應用密切相關，特別是計算複雜性理論和資料庫理論。數學邏輯的一個基本見解是，我們對數學現象的理解通過將我們用來描述數學結構的語言提升為明確研究的對象而得到豐富。如果數學是模式的科學，那麼我們辨識模式的媒介以及我們辨識它們的結構便引起了我們的注意。這正是邏輯在模型理論中最突出的方面，模型理論是數學邏輯的一個分支，處理形式語言及其解釋之間的關係。因此，數學邏輯，特別是有限模型理論，能在計算機科學中找到多種應用也就不足為奇了：從指定程式到查詢資料庫，計算機科學充滿了需要密切關注語言與結構之間互動的現象。本書提供了有限模型理論一些核心主題的廣泛概述：表達能力、描述複雜性和零一法則，並選擇性地應用於資料庫理論和人工智慧，特別是約束資料庫和約束滿足問題。最後一章提供了一個簡明的現代模態邏輯介紹，強調了與有限模型理論在精神和技術上的連續性。

Erich Graedel is a Professor of Mathematical Foundations of Computer Science at the University of Technology Aachen. His research interests include algorithms, complexity, and logic in computer science.

Phokion G. Kolaitis is a professor of computer science at the University of California, Santa Cruz. His current research interests include logic in computer science, computational complexity, and database theory. He earned a Diploma in Mathematics from the University of Athens, Greece in 1973, and a Ph.D. in Mathematics from the University of California, Los Angeles in 1978. Before joining UC Santa Cruz in 1988, he served as an L.E. Dickson Instructor of Mathematics at the University of Chicago, a faculty member at Occidental College, a visiting faculty member at Stanford University, and a visiting scientist at the IBM Almaden Research Center. Kolaitis was awarded a Guggenheim Fellowship during 1993-94. In 1995, he received an Excellence in Teaching Award by the graduating computer science and computer engineering students at UC Santa Cruz.

Leonid Libkin received his PhD from the University of Pennsylvania and is currently Professor of Computer Science at the University of Toronto. His main research interests include databases and applications of logic in computer science.

Maarten Marx is an associate professor at the Vrije Universiteit Amsterdam. His research interests are in modal and algebraic logic.

Joel Spencer is a Professor of Mathematics and Computer Scienceat the Courant Institute, New York University. His research interests lie in interface between Discrete Mathematics and Theoretical Computer Science, most particularly with the Probabilistic Method as developed by Paul Erdos.

Moshe Y. Vardi is a Noah Harding Professor of Computer Science and Chair of Computer Science at Rice University. Prior to joining Rice in 1993, he was at the IBM Almaden Research Center, where he managed the Mathematics and Related Computer Science Department. His research interests include database systems, computational-complexity theory, multi-agent systems, and design specification and verification. Vardi received his Ph.D. from the Hebrew University of Jerusalem in 1981. He is the author and co-author of over 120 technical papers, as well as a book titled "Reasoning about Knowledge". Vardi is the recipient of 3 IBM Outstanding Innovation Awards. He is an editor of several international journals and is a Fellow of the Association of Computing Machinery.

Yde Venema studied mathematics; in 1992, he received a PhD in Logic with the dissertation `Many-Dimensional Modal Logic'. He is currently a Research Fellow of the Royal Netherlands Academy of Arts and Sciences and an assistant professor at the Institute for Logic, Language and Computation of the University of Amsterdam. His research interests include modal and temporal logic, algebraic logic, and applications of logic in linguistics and computer science.

Scott Weinstein is Professor of Computer Science, Mathematics, and Philosophy at the University of Pennsylvania. His research interests include logic in computer science and the philosphy of mathematics.

Erich Graedel 是亞琛科技大學（University of Technology Aachen）計算機科學數學基礎的教授。他的研究興趣包括計算機科學中的演算法、複雜性和邏輯。

Phokion G. Kolaitis 是加州大學聖克魯斯分校（University of California, Santa Cruz）的計算機科學教授。他目前的研究興趣包括計算機科學中的邏輯、計算複雜性和資料庫理論。他於1973年在希臘雅典大學獲得數學文憑，並於1978年在加州大學洛杉磯分校獲得數學博士學位。在1988年加入加州大學聖克魯斯分校之前，他曾擔任芝加哥大學的L.E. Dickson數學講師、奧克西登塔爾學院的教職員、史丹佛大學的訪問教職員，以及IBM阿爾馬登研究中心的訪問科學家。Kolaitis在1993-94年期間獲得古根海姆獎學金。1995年，他獲得加州大學聖克魯斯分校計算機科學和計算機工程畢業生頒發的卓越教學獎。

Leonid Libkin 於賓夕法尼亞大學獲得博士學位，目前是多倫多大學的計算機科學教授。他的主要研究興趣包括資料庫和邏輯在計算機科學中的應用。

Maarten Marx 是阿姆斯特丹自由大學（Vrije Universiteit Amsterdam）的副教授。他的研究興趣在於模態邏輯和代數邏輯。

Joel Spencer 是紐約大學（New York University）庫朗數學與計算機科學研究所的數學與計算機科學教授。他的研究興趣位於離散數學與理論計算機科學之間的交界，特別是保羅·厄爾多斯（Paul Erdos）所發展的概率方法。

Moshe Y. Vardi 是萊斯大學（Rice University）的諾亞·哈丁計算機科學教授及計算機科學系主任。在1993年加入萊斯大學之前，他曾在IBM阿爾馬登研究中心工作，負責數學及相關計算機科學部門的管理。他的研究興趣包括資料庫系統、計算複雜性理論、多代理系統，以及設計規範和驗證。Vardi於1981年在耶路撒冷希伯來大學獲得博士學位。他是120多篇技術論文的作者和合著者，並著有一本名為《Reasoning about Knowledge》的書。Vardi曾獲得3項IBM傑出創新獎。他是幾本國際期刊的編輯，也是計算機協會（Association of Computing Machinery）的會士。

Yde Venema 學習數學；在1992年，他以論文《Many-Dimensional Modal Logic》獲得邏輯博士學位。他目前是荷蘭皇家藝術與科學學院的研究員，以及阿姆斯特丹大學邏輯、語言與計算研究所的助理教授。他的研究興趣包括模態邏輯和時間邏輯、代數邏輯，以及邏輯在語言學和計算機科學中的應用。

Scott Weinstein 是賓夕法尼亞大學的計算機科學、數學和哲學教授。他的研究興趣包括計算機科學中的邏輯和數學哲學。