The Undecidability of Boolean BI through Phase Semantics
The Undecidability of Boolean BI through Phase Semantics
复制标题
通过阶段语义判断布尔 BI 的不可判定性
DOI：
10.1109/lics.2010.18
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Galmiche
中科院分区：
文献类型：
--
作者：
Dominique Larchey;D. Galmiche
我们解决了布尔BI逻辑（BBI）可决定性的开放问题，该问题可被视为分离和空间逻辑的核心。为此，我们为BBI定义了完整的阶段语义，并将其表征为琐碎的相位语义。我们推断出用于直觉线性逻辑（ILL）的琐碎相语义语义和BBI的Kripke语义。我们挑出了一个生病的片段，该片段既无法确定又完整。因此，我们获得了BBI的不可证明性。
We solve the open problem of the decidability of Boolean BI logic (BBI), which can be considered as the core of separation and spatial logics. For this, we define a complete phase semantics for BBI and characterize it as trivial phase semantics. We deduce an embedding between trivial phase semantics for intuitionistic linear logic (ILL) and Kripke semantics for BBI. We single out a fragment of ILL which is both undecidable and complete for trivial phase semantics. Therefore, we obtain the undecidability of BBI.