Complexity and Nicety of Fluted Logic
Complexity and Nicety of Fluted Logic
复制标题
凹槽逻辑的复杂性和精细性
DOI：
10.1023/a:1016596721799
复制
发表时间：
2002
期刊：
影响因子：
0.7
通讯作者：
W. C. Purdy
中科院分区：
文献类型：
--
作者：
W. C. Purdy
凹槽逻辑本质上是没有变量的一阶谓词逻辑。缺乏变量会导致表达能力下降。然而，许多可以用自然语言表述的逻辑问题，如著名的舒伯特的《压路机》，可以用长笛逻辑来表达。槽纹逻辑的表现力的进一步证据是它与描述逻辑的密切关系。已经证明，槽纹逻辑是可判定的，并且具有有限模型性质。本文证明了凹槽逻辑具有指数模型性质，判定可满足性是NEXPTIME-完全的。进一步证明了槽纹逻辑是“好的”，即它与一阶谓词逻辑共享插值性质和模型保持性质。
Fluted Logic is essentially first-order predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finite-model property. This paper shows that fluted logic has the exponential-model property and that deciding satisfiability is NEXPTIME-complete. It is shown further that fluted logic is 'nice’, that is, it shares with first-order predicate logic the interpolation property and model preservation properties.