| 二阶扩展逻辑的复杂性与表达能力 |
| |
| 引用本文： | 冯世光,赵希顺.二阶扩展逻辑的复杂性与表达能力[J].逻辑学研究,2012(1):11-34. |
| |
| 作者姓名： | 冯世光 赵希顺 |
| |
| 作者单位： | 中山大学逻辑与认知研究所 |
| |
| 基金项目： | supported by the NSFC project under grant No.60970040;the MOE project under grant No.11JJD720020 |
| |
| 摘 要： | 本文研究了在所有有穷结构上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 结构 证明 程序 版本 |
The Complexity and Expressive Power of Second-Order Extended Logic |
| |
| Shiguang Feng Institute of Logic and Cognition,Sun Yat-sen University Xishun Zhao.The Complexity and Expressive Power of Second-Order Extended Logic[J].Studies in Logic,2012(1):11-34. |
| |
| Authors: | Shiguang Feng Institute of Logic and Cognition Sun Yat-sen University Xishun Zhao |
| |
| Institution: | Institute of Logic and Cognition,Sun Yat-sen University |
| |
| Abstract: | We study the expressive powers of SO-HORN*,SO-HORN*r and SO-HORN*r on all finite structures.We show that SO-HORNr,SO-HORN*r,FO(LFP) coincide with each other and SO-HORN* is proper sublogic of SO-HORNr.To prove this result,we introduce the notions of DATALOG* program,DATALOGr program and their stratified versions,S-DATALOG program and S-DATALOGr program.It is shown that,on all structures,DATA-LOGr and SDATALOGr are equivalent and DATALOG* is a proper sublogic of DATALOGr.SO-HORN* and SO-HORNr can be treated as the negations of DATALOG and DATALOGr,respectively.We also show that SO-EHORNr logic which is an extended version of SO-HORN captures co-NP on all finite structures. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 等数据库收录！ |
