论文标题
分支分支的积极轩尼诗 - 米尔纳逻辑
Positive Hennessy-Milner Logic for Branching Bisimulation
论文作者
论文摘要
可以根据模态逻辑和一分化来研究标记的过渡系统。这两个概念由Hennessy-Milner定理连接，这表明当两个状态满足相同的模态逻辑公式时，两个状态是偶然的。最近，已将Atartness作为双仿真的研究，这也引起了Hennessy-Milner定理的双重版本：两个状态在有一个模态公式区分时，正好是两个状态。 在本文中，我们介绍了Hennessy-Milner定理的“定向”版本，这些版本是一种何时包含在另一个状态的理论时。为此，我们介绍了仅允许有限使用否定的“积极模态逻辑”。此外，我们介绍了有指导性的一分子和公寓概念，然后表明，对于这种积极的模态逻辑，$ s $的理论恰恰包含在$ t $的理论中。或者，就公寓而言，我们表明$ s $是指$ t $的指向$ s $的理论不包括在$ t $的理论中。从轩尼诗 - 米勒纳定理的指示版本中，最初的结果如下。 特别是，我们研究了分支分支和轩尼诗 - 米勒纳逻辑的情况，直到（HMLU）作为模态逻辑。我们介绍了“定向分支双仿真”（并定向分支分离）和“正轩尼诗 - 米尔纳逻辑，直到（PHMLU），我们展示了Hennessy-Milner定理的定向版本。在此过程中，我们表明每个HMLU公式都等同于阳性HMLU公式的布尔组合，这是一个非常不平淡的结果。这引起了HMLU的sbobloic，它同样表达但更容易推理。
Labelled transitions systems can be studied in terms of modal logic and in terms of bisimulation. These two notions are connected by Hennessy-Milner theorems, that show that two states are bisimilar precisely when they satisfy the same modal logic formulas. Recently, apartness has been studied as a dual to bisimulation, which also gives rise to a dual version of the Hennessy-Milner theorem: two states are apart precisely when there is a modal formula that distinguishes them. In this paper, we introduce "directed" versions of Hennessy-Milner theorems that characterize when the theory of one state is included in the other. For this we introduce "positive modal logics" that only allow a limited use of negation. Furthermore, we introduce directed notions of bisimulation and apartness, and then show that, for this positive modal logic, the theory of $s$ is included in the theory of $t$ precisely when $s$ is directed bisimilar to $t$. Or, in terms of apartness, we show that $s$ is directed apart from $t$ precisely when the theory of $s$ is not included in the theory of $t$. From the directed version of the Hennessy-Milner theorem, the original result follows. In particular, we study the case of branching bisimulation and Hennessy-Milner Logic with Until (HMLU) as a modal logic. We introduce "directed branching bisimulation" (and directed branching apartness) and "Positive Hennessy-Milner Logic with Until" (PHMLU) and we show the directed version of the Hennessy-Milner theorems. In the process, we show that every HMLU formula is equivalent to a Boolean combination of Positive HMLU formulas, which is a very non-trivial result. This gives rise to a sublogic of HMLU that is equally expressive but easier to reason about.
