• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Order-Invariance of Two-Variable Logic is Decidable
【24h】

Order-Invariance of Two-Variable Logic is Decidable

机译：二变量逻辑的阶不变性是可确定的

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

It is shown that order-invariance of two-variable first-logic is decidable in the finite. This is an immediate consequence of a decision procedure obtained for the finite satisfiability problem for existential second-order logic with two first-order variables (ESO2) on structures with two linear orders and one induced successor. We also show that finite satisfiability is decidable on structures with two successors and one induced linear order. In both cases, so far only decidability for monadic ESO2 has been known. In addition, the finite satisfiability problem for ESO2 on structures with one linear order and its induced successor relation is shown to be decidable in non-deterministic exponential time.
机译：结果表明，二元第一逻辑的阶不变性是有限的。这是针对具有两个一阶变量（ESO）的存在二阶逻辑的有限满足性问题而获得的决策程序的直接结果。 2 ）在具有两个线性阶和一个诱导后继的结构上。我们还表明，在具有两个后继和一个感应线性阶数的结构上，可以确定有限的可满足性。在这两种情况下，到目前为止，仅对单原子ESO的可判定性 2 已经知道了。此外，ESO的有限可满足性问题 2 具有一阶线性结构的结构及其诱导的后继关系在不确定的指数时间内被确定。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号