代码之家 › 专栏 › 技术社区 › cmoses

在自旋ltl公式中使用(U)ntil算子

promela spin model-checking

2

cmoses · 技术社区 · 7 年前

我试图理解如何在ltl公式中正确使用Until运算符。我找到了 this

U

B: 如果存在i,则为true:

s _i+1 _i+2 , ]

_j s _j+1 s _j+2 ,

含义:

B在时间i时为真

仍然使用“true at time i”的形式化

示例ltl公式的示例代码:

mtype = {Regular, Reverse, Quit}

mtype state = Regular;

init {
do ::
   if
   ::state == Regular -> state = Reverse
   ::state == Reverse -> state = Quit
   ::state == Quit -> break
   fi
od
}

ltl p0 { [] ((state == Reverse) U (state != Reverse))}

基于我给出的直到算子的定义,我不理解上面的ltl公式是如何不产生任何错误的。不会 state == Reverse 需要一直保持真实,直到 state != Reverse state == Regular .

以下是运行测试后的自旋输出:

(Spin Version 6.4.6 -- 2 December 2016)
    + Partial Order Reduction

Full statespace search for:
    never claim             + (p0)
    assertion violations    + (if within scope of claim)
    acceptance   cycles     + (fairness disabled)
    invalid end states  - (disabled by never claim)

State-vector 28 byte, depth reached 13, errors: 0
        9 states, stored (11 visited)
        2 states, matched
       13 transitions (= visited+matched)
        0 atomic steps
hash conflicts:         0 (resolved)

Stats on memory usage (in Megabytes):
    0.000   equivalent memory usage for states (stored*(State-vector + overhead))
    0.288   actual memory usage for states
  128.000   memory used for hash table (-w24)
    0.534   memory used for DFS stack (-m10000)
  128.730   total actual memory usage


unreached in init
    (0 of 12 states)
unreached in claim p0
    _spin_nvr.tmp:14, state 20, "-end-"
    (1 of 20 states)

pan: elapsed time 0 seconds

1 回复 | 直到 7 年前

1

2

Patrick Trentin 7 年前

强大到

它的是:

M、 s _k

<-&燃气轮机;

j.N。

(j k)§

_一、 _i+1

(米,秒 _j

_一、

M是Kripke结构

_t

说明:

(1)-(2) _k _k+1 , ..., s , ...) 作为转换系统的有效执行路径可以计算公式。
条件军队 Ï 在s中保持 _j
(4) 军队 Ï 州s _一、最多s _j (不包括)

因为一个带有 false true 逻辑蕴涵 (4) 是微不足道的对于任何 i 超出范围 [k, j) . 无论何时 j k ,如您所问,范围 [k, j) = [k, k) 是空的,可以选择 一、 M, s â¨ Ï 持有对于一些人来说 s 条件对任何选择都非常满意并且它不再对执行路径施加任何约束 _k , ..., s _j , ...). 换句话说,当 j = k 条件 (4) 不再为财产验证提供任何有意义的贡献 Ï U Ï _k

弱到

之间的差异 ,在此表示为 Ï W Ï 和是吗弱到 G (Ï â§ Â¬Ï) 鉴于强迫 F Ï .

p0

[] ((state == Reverse) U (state != Reverse))

((state == Reverse) U (state != Reverse))

保持系统的每一个状态。我会崩溃的为清晰起见,分为两个部分,并定义 state == Reverse 和 state != Reverse Ï <-> !Ï

s_0 :常规状态,也恰好是 初始状态
:反向状态
s_2 :最终状态

p0 要保持, p1

处于状态 s_0 财产因此,保持也适用于 j 相同的 0 .
财产 假 s_2 p1 s_1 .
s_2 财产是 真的 所以再一次微不足道的满足。