二阶扩展逻辑的复杂性与表达能力

摘要：

本文研究了在所有有穷结构上SO．HORN＊，SO—HORNτ和SO-HORNτ的表达能力。我们证明了SO-HORNτ，SO—HORN＊τ和FO（LFP）的表达能力是一致的，SO—HORN＊是SO-HORNτ的一个严格子逻辑。为了证明这一结果，我们提出了DATALOG＊程序，DATALOGτ程序以及它们的分层版本S-DATALOG＊程序利S-DATALOGτ程序。我们证明了在所有有穷结构上DATALOGτ和S-DATALOGτ是等价的，并且DATALOG。足DATALOGτ的一个严格子逻辑。最后我们还用两种方法证明了SO-HORN的一个扩展版本SO—EHORNτ逻辑可以在所有有穷结构有有结构上刻画co—NP。

关键词：表达能力、逻辑、复杂性、SO、结构、证明、程序、版本

所属期刊栏目：5

分类号：B81(逻辑学(论理学))

资助基金：The research was partially supported by the NSFC project under grant No. 60970040 and the MOE project under grant No. 11JJD720020

在线出版日期：2012-08-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共24页

页码：11-34