logo标签列表

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

mathcomputer-sciencelogicautomata
13
我知道这更像是一个数学/形式语言/自动机/计算机科学问题，而不是编程问题，但我希望能够获得一本易懂的教材（而不是晦涩难懂的专著），介绍除命题演算和谓词演算外的形式逻辑。我对单调二阶逻辑和Büchi自动机特别感兴趣。
目前，我只找到了Automata theory and its applications by Bakhadyr Khoussainov, Anil Nerode. Automata, logics, and infinite games By Erich Grädel, Thomas Wilke (eds). 和Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic Benedikt Bollig……对我来说太过深奥。
我发现这篇论文是一个很好的补充资源：无限输入有限状态自动机，作者是Madhavan Mukund（http://www.cmi.ac.in/~madhavan/papers/tcs-96-2.html）。这篇论文更多地涉及布氏自动机而非单调二阶逻辑。 - anno
我接近了：Leonid Libkin的《有限模型理论元素》（http://books.google.com/books?id=zsJlEK4nK7sC）几乎可以阅读。 - anno
我不太确定这两个主题之间的联系有多紧密。单调二阶逻辑是数学的一部分，特别是元数学（基础、逻辑和集合论）。布奇自动机来自计算机科学、可计算性理论，我想。我意识到计算机科学和数学仍然非常接近，但我真的不明白为什么你希望会有一本关于这两个主题的书。 - RBarryYoung
无限对象上的自动机是由Buchi在20世纪60年代初引入的，其动机是数学逻辑中的问题，即他单继承二阶理论（S1S）的可决定性。[...]到20世纪60年代末，Rabin已经展示了如何使用无限树上的自动机来展示一类令人惊讶的丰富的逻辑理论的可确定性，包括多继承基本单继承二阶理论（SnS）。 出自Emerson, Buchi 自动机在计算科学中的作用 - anno
我发现了这篇有趣的论文: Wolfgang Thomas的“语言，自动机和逻辑”(http://www.cs.uiuc.edu/class/fa05/cs598mp/LangAutomataLogic.pdf)。关键词: 有限自动机，单调二阶逻辑，Büchi自动机。数学内容仍然有些晦涩，但通过一些努力是可以理解的(我想)。 - anno
还好。但是，它非常深奥，整本书似乎很难实现，特别是如果你只限于英语。论文似乎更有可能。但是你可能会走运... :-) - RBarryYoung
6个回答
6

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

逻辑学初学者：

Peter J. Cameron，《集合、逻辑和范畴》，Springer，Springer Undergraduate Mathematics Series，1999年，URL。

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

面向计算机科学家的逻辑学。

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

Michael Sipser，《计算理论导论》，Course Technology出版，2005年（第2版），URL。

和

Alan P. Parkes，《语言、机器和逻辑导论》，Springer，2002年。

和

Peter Linz，《形式语言与自动机导论》，Jones & Bartlett Publishers，2000年（第3版）URL。

和

John E. Hopcroft和Jeffrey D. Ullman，《自动机理论、语言和计算机导论》，Addison Wesley，1979年（第1版），ISBN：0-201-02988-X；URL。

中级逻辑（本科）：

D. Ebbinghaus，《数学逻辑》，Springer，URL。

或者

Elliott Mendelson，《数理逻辑导论》URL

高级水平（研究生）：

Wolfgang Thomas，《语言、自动机和逻辑》URL，1996年。

Leoni Libkin，《有限模型理论要素》Springer，2004年，URL，TOC。

研究用：

Benedikt Bolli，《通信系统的形式模型》，Springer，2006年，URL。

Grädel, Erich; Thomas, Wolfgang; Wilke, Thomas (编者)，《自动机、逻辑和无限游戏》，Springer，2002年，URL，

2

您似乎对书中的某个特定主题有兴趣，因此我查看了亚马逊上一些书籍的索引。虽然我从未阅读过这本书，但 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

覆盖内容在《无限字符串与S1S的自动机》第25讲中，第一页可从链接处预览。 《计算理论》http://ecx.images-amazon.com/images/I/51JKHJGWBRL._BO2,204,203,35,-76_AA240_SH20_OU01_.jpg。
这本书看起来很有趣，但是讲座的格式、大量（不相关）的主题以及 S1S 的呈现稀少使它不是一个非常好的解决方案。 - anno
Wolfgang Thomas的《Languages, Automata and Logic》是我目前找到的最好的演示。 - anno
2

我听说过Michael Sipser的计算理论导论很不错。实际上，我现在就把它放在眼前，尽管我还没有开始阅读。

Spiser的《自动机理论、语言和计算》是一本非常好的书，但它非常基础，没有涉及形式逻辑。我的标题有点误导人。仅仅是单调二阶逻辑和Büchi自动机之间存在关系。 - anno
我个人觉得那本书有点令人困惑——例子太“完美”了，而且图表/例子的解释不如我所希望的那样清晰。在我看来！ - poundifdef
0

这可能不完全是您要寻找的，但我从Blackburn等人的模态逻辑中学到了很多东西，而我所知道的自动机则来自于Jurafsky和Martin的语音和语言处理，尤其是第2章。如果没有其他的，两者都为进一步研究提供了良好的基础。

我知道《语音和语言处理》这本书，但那不是我想要的 :) 但我会看看 Blackburn 的书。 - anno
0

我记得在模型检验原理中读到了布氏自动机的相关内容，这是一本非常好的书。当然，它的重点是应用于模型检验，但模型检验本质上就是逻辑。

我已经找到了《TOC》（http://www.ulb.tu-darmstadt.de/tocs/19825007X.pdf），这本书本身看起来很有趣，但我担心“模型检查”偏见不是我所寻找的。需要怎样的数学成熟度才能浏览它？ - anno
0

你可能有些惊讶，但我认为你正在寻找的书籍是《数据库基础》(Foundations of Databases)，它是由阿比特布尔(Abiteboul)、哈尔(Hull)和维亚努(Vianu)撰写的（也被称为“爱丽丝书”，因为爱丽丝在封面上绘画，并在章节介绍对话中与作者一起担当主角）。这不是一本关于SQL的书，而是关于数据库理论的书籍--逻辑及其在程序和函数中的实现--因此它花费了相当多的篇幅来探讨查询语言的复杂性和可计算性问题；而且作者们非常友好和通俗易懂。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接