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

我知道这更像是一门数学/形式语言/自动机/计算机科学问题,而不是编程问题,但我希望我能在关于命题和谓词微积分之外的形式逻辑上得到一些关于 comprehensible textbook (不是难以理解的专着)的建议 . 我对 monadic second order logicBüchi Automata 特别感兴趣 .

现在,我只找到了Bakhadyr Khoussainov,Anil Nerode的Automata theory and its applications . Automata, logics, and infinite games作者:ErichGrädel,Thomas Wilke(编辑) . 并且Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic Benedikt Bollig ......我的头脑 .

回答(6)

2 years ago

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

For Beginners in Logic :

Peter J. Cameron,集合,逻辑和类别,Springer,Springer本科数学系列,1999,URL .

James L. Hein,Discrete Structures,Logic and Computability,Jones&Bartlett Publishers,2009(第3版)URL .

计算机科学家的逻辑 .

For Beginners in Automata and Formal Langugage :

Michael Sipser,计算理论导论,课程技术,2005(第二版),URL .

and

Alan P. Parkes,语言,机器和逻辑导论,Springer,2002年 .

and

Peter Linz,正式语言和自动机的介绍,Jones&Bartlett Publishers,2000(3 ed)URL .

and

John E. Hopcroft和Jeffrey D. Ullman,Automata Theory,Languages and Computation Introduction,Addison Wesley,1979,(第1版),ISBN:0-201-02988-X; URL .

Intermediate level Logic (undergraduate):

D. Ebbinghaus,数学逻辑,Springer,URL .

or

Elliott Mendelson,数学逻辑导论,URL

Advanced level (Graduate):

Wolfgang Thomas,Languages, Automata and Logic,1996 .

Leoni Libkin,有限模型理论的要素,Springer,2004,URLTOC .

For Research

Benedikt Bolli,通信系统的正式模型,Springer,2006,URL .

格雷德尔,埃里希;托马斯,沃尔夫冈;威尔克,托马斯(编辑),自动机,逻辑和无限游戏,Springer,2002,URL

2 years ago

我've heard good things about Michael Sipser' s Introduction to the Theory of Computation . 我实际上把它放在我面前,虽然我还没有开始阅读它 .

2 years ago

您似乎从书中找到了您想要的特定主题,因此我查看了亚马逊中某些书籍的索引 . 虽然我从未读过这本书,但是Dexter C. Kozen的Theory of Computation可能会让你感兴趣 .

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

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

覆盖的页面位于Lecture 25 Automata on Infinite Strings and S1S,第一页可从链接预览 .

Theory of Computation http://ecx.images-amazon.com/images/I/51JKHJGWBRL.BO2,204,203,35,-76_AA240_SH20_OU01.jpg

2 years ago

这可能不是你所知道的,我从Jurafsky和Martin的_757452中了解到我对自动机的了解,尤其是 . 第2章 . 如果不出意外,两者都为进一步研究提供了良好的基础 .

2 years ago

我记得在Principles of Model Checking读过关于BüchiAutomata的文章,这本书看起来很不错 . 当然,重点是模型检查的应用,但模型检查主要是逻辑 .

2 years ago

你会有点惊讶,但我认为你正在寻找的书是Abiteboul,Hull和Vianu的数据库基础(也被称为“爱丽丝书”,因为爱丽丝被封面和星星在章节介绍对话与作者) . 它不是一本关于SQL的书,而是关于数据库理论 - 逻辑及其在程序和函数中的实现 - 因此它在查询语言的复杂性和可计算性问题上花费了很多;并且作者努力做到友好和沟通 .