论文部分内容阅读
本文研究了在所有有穷结构上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τ的一个严格子逻辑。最后我们还用两种