• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Modal independence logic
【24h】

Modal independence logic

机译：模态独立逻辑

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This article introduces modal independence logic MIL, a modal logic that can explicitly talk about independence among propositional variables. Formulas of MIL are not evaluated in worlds but in sets of worlds, so called teams. In this vein, MIL can be seen as a variant of Vaananen's modal dependence logic MDL. We show that MIL embeds MDL and is strictly more expressive. However, on singleton teams, MIL is shown to be not more expressive than usual modal logic, but MIL is exponentially more succinct. Making use of a new form of bisimulation, we extend these expressivity results to modal logics extended by various generalized dependence atoms. We demonstrate the expressive power of MIL by giving a specification of the anonymity requirement of the dining cryptographers protocol in MIL. We also study complexity issues of MIL and show that, though it is more expressive, its satisfiability and model checking problem have the same complexity as for MDL.
机译：本文介绍了模态独立逻辑MIL，这是一种模态逻辑，可以明确地讨论命题变量之间的独立性。 MIL的公式不在世界范围内评估，而是在世界范围内评估，即所谓的团队。从这个角度来看，MIL可以看作是Vaananen的模态依赖逻辑MDL的变体。我们证明MIL嵌入了MDL并且严格地更具表现力。但是，在单例团队中，MIL的表现力并不比通常的模态逻辑高，但MIL的指数级更为简洁。利用一种新的双仿真形式，我们将这些表示结果扩展到由各种广义依赖原子扩展的模态逻辑。我们通过给出MIL中就餐密码学家协议的匿名性要求的规范来证明MIL的表达能力。我们还研究了MIL的复杂性问题，并表明，尽管它更具表达性，但其可满足性和模型检查问题的复杂性与MDL相同。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号