高级形式逻辑/自动机理论教科书

Question

我知道这更像是一个数学/形式语言/自动机/计算机科学问题，而不是编程问题，但我希望我能就一本关于形式逻辑的易于理解的教科书（而不是难以理解的专着）获得一些建议超越命题和谓词演算。 我对一元二阶逻辑和Büchi Automata特别感兴趣。

目前，我只找到了 Bakhadyr Khoussainov、Anil Nerode 所著的自动机理论及其应用 。 自动机、逻辑和无限游戏作者：Erich Grädel、Thomas Wilke（编辑）。 以及通信系统的形式模型：语言、自动机和单子二阶逻辑 Benedikt Bollig...这超出了我的能力范围。

Answer 1

所以这是我能提供的最好的课程：

逻辑初学者：

Peter J. Cameron，集合、逻辑和范畴，Springer，Springer 本科数学系列，1999 年， 网址。

James L. Hein，离散结构、逻辑和可计算性，Jones & Bartlett 出版社，2009 年（第 3 版）URL。

计算机科学家的逻辑。

对于自动机和形式语言初学者：

Michael Sipser，计算理论导论，课程技术，2005 年（第 2 期），URL。

和

Alan P. Parkes，语言、机器和逻辑简介，Springer，2002。

和

Peter Linz，简介形式语言和自动机，Jones & Bartlett 出版社，2000 年（第 3 版）URL。

和

John E. Hopcroft 和 Jeffrey D. Ullman，自动机理论、语言和计算简介，Addison Wesley，1979 年，（第一版），ISBN ：0-201- 02988-X； 网址。

中级逻辑（本科）：

D. Ebbinghaus、数学逻辑、Springer、URL。

或

Elliott Mendelson，数理逻辑导论，URL

高级（研究生）：

Wolfgang Thomas，语言、自动机和逻辑，1996。Leoni

Libkin，元素有限模型理论，Springer，2004 年，URL，目录。

用于研究

Benedikt Bolli，通信系统的形式模型，Springer，2006，网址。

埃里希·格拉德尔； 托马斯，沃尔夫冈； Wilke, Thomas（编辑），自动机、逻辑和无限游戏，Springer，2002，网址，

Answer 2

我听说过 Michael Sipser 的计算理论简介。 事实上，它就在我面前，尽管我还没有开始阅读它。

Answer 3

您似乎想从一本书中找到特定的主题，所以我查看了亚马逊上一些书籍的索引。 虽然我从未读过这本书，但 Dexter C 所著的计算理论 Kozen 可能会让您感兴趣。

Büchi automation, 155, 159, 161, 283, 298, 343
      determinization, 167-170

monadic second-order theory
    of n successors, 154
    of successor, 154-159

涵盖的页面位于第25讲无限字符串和S1S自动机中，第一页可用从链接预览。

计算理论 http://ecx. images-amazon.com/images/I/51JKHJGWBRL._BO2,204,203,35,-76_AA240_SH20_OU01_.jpg

Answer 4

这可能不是您想要的，但我从 Blackburn 等人的 模态逻辑，我从 Jurafsky 和 ​​Martin 的语音和语言处理< /a>，特别是。 第二章。如果不出意外的话，两者都为进一步的研究提供了良好的基础。

Answer 5

我记得在 模型检查原理< /a>，这似乎是一本相当不错的书。 当然，重点是模型检查的应用，但模型检查无论如何主要是逻辑。

Answer 6

你可能会有点惊讶，但我认为你要找的书是 Abiteboul、Hull 和 Vianu 所著的《数据库基础》（也称为“爱丽丝书”，因为爱丽丝被画在封面上，星星是章节介绍与作者的对话）。 这不是一本关于 SQL 的书，而是关于数据库理论——逻辑及其在程序和函数中的实现——所以它在查询语言的复杂性和可计算性问题上花了很多钱； 作者们努力保持友好和沟通。