没有合适的资源?快使用搜索试试~ 我知道了~
蒙特卡罗模型检验与过程代数问题
理论计算机科学电子笔记162(2006)203-207www.elsevier.com/locate/entcs进程代数Radu Grosu和Scott A. 斯莫尔卡部石溪大学计算机科学 Stony Brook,NY,11794,USA电子邮件:{grosu,smolka}@ cs.sunysb.edu摘要我们回顾了最近开发的蒙特卡罗模型检测技术,并展示了它如何可以应用到I/O自动机的实现问题。然后,我们考虑一些开放的问题,在应用蒙特卡罗技术的其他过程代数问题,如模拟和互模拟。关键词:蒙特卡罗模型检验,I/O自动机,模拟,互模拟1介绍蒙特卡罗方法经常用于工程和计算机科学应用中,以计算解的近似值,其精确计算证明是易于处理的。示例应用包括贝叶斯网络中的信念更新最近,模型检验的研究人员已经转向蒙特卡洛方法,以应对状态爆炸的问题;例如,见[3,6,8,1]。 本文回顾了文献[1]中的Monte Carlo模型检验算法,并展示了如何将其应用于I/O自动机的实现问题[4]。 然后,我们考虑一些开放的问题,在应用蒙特卡罗技术的其他过程代数问题,如模拟和互模拟。2蒙特卡罗模型检验MonteCarlo 模型检验是在 文献[1]中提出的一种新技术,它利用离散的 Bu ?chiatomaton(BA)中的随机抽样来实现LTL模型检验的一种简单、我们的方法利用Vardi和Wolper [7]的自动机理论技术中的以下思想进行LTL模型检查:给定有限状态系统和LTL的指定S1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2006.04.033204R. Grosu,S.A.Smolka/Electronic Notes in Theoretical Computer Science 162(2006)203对于mulanumb,S|如果B = B S × B <$的B u?h i auau age的长度是有效的,则B = BS×B<$的长度是有效的。 BS是Bu�chiau,它负责在S的状态转移过程中恢复S,而B�c是B u�ch i a u,它负责对B�c的调节。一个从初始状态B可到达的循环一个套索,并说套索接受如果套索的循环部分包含最终状态B。在B中存在一个接受套索意味着S不是一个接受套索的模型。此外,这样一个可接受的套索可以被看作是S的反例|= 0。因此,LTL模型检验问题自然地被定义为B=BS×B的BA空性问题,这简化为在B中找到接受套索。我们不是搜索B的整个状态空间来接受套索,而是通过在中执行均匀随机游走,在空间上连续生成B的M个套索。B.如果当前生成的套索是接受的,我们就找到了空的反例,然后我们停止。我们需要生成的套索数量M取决于两个参数:误差容限和置信度δ。为了确定M,对于给定的ε和δ,我们的目标是在置信度1-δ和误差ε内回答以下问题:我们需要产生多少个独立的套索,直到其中一个 接受? 答案是基于一个几何随机变量X和统计假设检验。几何随机变量由伯努利随机变量Z(在本节后面定义)参数化,它以概率pZ取值1,以概率qZ= 1−pZ取值0。直觉上,pZ是B的任意套索接受的概率。对 于Z 的 N 次 独 立 试 验 , X 的 累 积 分 布 函 数 为 : F ( N ) =P[X≤N] = 1−(1−pZ)N。 要求F(N)= 1 −δ得到:N = ln(δ)/ln(1 −p Z)。因为pZ是我们 想 要 确 定 的 , 所 以 我 们 假 设 pZ≥π 。 将 pZ 替 换 为 n , 得 到 M= ln ( δ ) /ln(1−n),它大于N,因此P[X≤M]≥P[X≤N]= 1−δ。总结:pZ≥P[X≤M]≥ 1−δ其中M = ln(δ)/ln(1−δ)(1)不等式1给出了在假设pZ≥δ的情况下,达到成功所需的最小尝试次数M。排除这种假设的标准方法是使用统计假设检验,将零假设H0定义为pZ≥0的假设。重写不等式1关于H0,我们得到:P [X≤M|H0] ≥ 1 − δ(2)我们现在进行M次试验。如果没有找到反例,即,如果X> M,我们拒绝H0。这可能会引入第一类错误:即使我们没有找到反例,H0也然而,产生这种错误的概率由δ限定;这在不等式3中示出,其通过在不等式2中取X≤M的补数而获得:P [X > M|H0] <δ(3)伯努利随机变量Z与均匀随机游走概率空间(P(L),P)相关联。 样本空间L是B的所有套索的集合;La和Ln分别是B的所有接受套索和非接受套索的集合R. Grosu,S.A.Smolka/Electronic Notes in Theoretical Computer Science 162(2006)2032051234套索的概率P [σ] σ = S0e0. S n−1e n−1S n归纳定义如下:P [S0] = k−1,如果|S0|= k和P [S0e0.. S n−1e n−1S n] = P [S0e0. S n−1]·π [S n−1e n−1S n]其中π [Se SJ] =m−1,如果(S,e,SJ)∈E,且|英(西)|= m。示例2.1[套索的制造]ConsidertheBu?chiautomamatonBofFigure1. 它包括四个编号11、1244、1231和12344,具有1/2、1/4、1/8和1/8的容量。 1231号电梯正在运行。Fig. 1. 示例套索概率空间。定义2.2[Lasso Bernoulli变量]与B中B的随机变量的概率spac(P(L),P)相关的随机变量Z定义如下:pZ=Σ ΣP[Z= 1]=λa∈LaP[λa]且qZ=P[Z= 0]=λn∈LnP [λ n].示例2.3[LassosBernoulivariab在定义了Z、X和H0之后,我们现在准备介绍MC2,这是我们用于BA空性检验的蒙特卡罗决策过程其伪码在下面给出,其中rInit(B)=random(S0),rNext(B,S)=random(E(S)),并且acc(S,B)=(S∈F).MC2算法输入: B=(S,S0,E,F);0<δ<1;0<δ<1。output:(false,接受lasso l)或(true,“P [X > M|H0]<δ“)(一)M:=lnδ/ln(1−1);(2)for(i:= 1;i≤M; i++)if(RL(B)==(1,l))return(false,l);(3)return(true,“P [X > M|H0]<δ“);主程序由三个语句组成,其中第一个语句使用不等式1来确定M的值,给定参数δ和δ。 第二个语句 是一个for循环,它通过调用random lasso(RL)例程连续采样M个套索。如果找到接受套索l,MC2判定为假并返回l作为反例。如果在M次试验中没有发现接受套索,MC2决定为真,并报告概率小于δ,pZ> δ。RL例程通过使用rInit(rInit)和rNext(rNext)例程生成随机套索。为了确定所生成的套索是否正在接受,它将每个遇到的状态s的索引i存储在HashTbl中,并将最近遇到的接受状态的索引记录在变量f中。 一旦检测到周期,即,状态s:=rNext(B,s)在HashTbl中,它检查HashTbl(s)是否≤f;当且仅当是这种情况时,循环是接受循环。函数lasso()从存储在HashTbl中的状态中提取lasso。通过按需生成随机状态rInit(B)和rNext(B,s),并符号化地执行验收acc(B,s)测试,在B上生成一个针对B的Bu-hiA的测试,从而可以在B上显式地构造B206R. Grosu,S.A.Smolka/Electronic Notes in Theoretical Computer Science 162(2006)203MC2是非常有效的。它在时间上运行O(MD),使用O(D)空间,其中M是最优的,D是B3I/O自动机I/O自动机(IOA)是一种有限状态自动机,其转换与命名动作相关联,这些动作被分类为输入,输出或内部。 输入和输出动作用于与自动机的环境进行通信假设输入动作不受自动机见[4],见[5],见[6]。I/O Automata(IOA)的实现问题如下。给定IOAA和B,代表被调查系统的实现和规范,A是否实现B(A≤B)?现在,如果L(A)<$L(B),则A≤B成立;也就是说,A的迹是B的迹的子集。这进而方程L(A×B)=λ,其中B是B的互补项. 因此,如果A的可观察行为是B的可观察行为,则没有A的可观察行为是B的可观察行为。通过将其状态的子集视为接受,可以将SPECIFICATIO AB定义为(输入的)Bu?chiAtomaton,将IOAA可以类似地被视为BA(其所有州都接受)。因此,IOA实现问题可以归结为BA的语言空性问题,并且可以直接应用MC2最近的一篇论文[2]建议如何将这一切扩展到时间I/O自动机的情况。4开放题将我们的蒙特卡罗方法扩展到分支时间时态逻辑的模型检查问题,如CTL,模态μ演算和Hennessy-Milner逻辑,这将是有趣的。这个扩展似乎是不平凡的,因为在乘积图中采样接受套索的想法将不再成立。出于类似的原因,在决定模拟[5]和互模拟中应用蒙特卡罗方法的问题仍然是开放的。引用[1] R. Grosu和S. A.斯莫尔卡蒙特卡洛模型检验。在TACAS 2005的会议记录中。Springer-Verlag,2005.[2] R. Grosu,S. A.斯莫尔卡湾Tan,A. Bouajjani,M. D. Bozga和S. Tripakis。时间自动机的蒙特卡罗模型检验,2005。已提交出版。[3] 你好,R。 Lass ai gne,F. 我是说,我是说。 你好。一个prox im atepr oi s ticmodelchecking。第五届国际验证、模型检查和抽象解释会议(VMCAI 2004),2004年。R. Grosu,S.A.Smolka/Electronic Notes in Theoretical Computer Science 162(2006)203207[4] N. Lynch和M.塔特尔输入/输出自动机简介。CWI Quarterly,2(3):219-246,1989.[5] N. Lynch和F.凡德拉格正向与反向模拟I:不计时系统。信息计算,121(2):214[6] K. Sen,M.Viswanathan和G.啊哈随机系统的统计模型检验在K. Etessami和S.Rajamani,编辑,第17届计算机辅助验证国际会议,LNCS第3576卷。施普林格,2005年。[7] M. Vardi和P. Wolper。自动程序验证的自动机理论方法。在Proc. IEEE Symposium on Logic in Computer Science,第332-344页,1986年。[8] HLS尤尼斯黑箱系统的概率验证。在K。Etessami和S. Rajamani,编辑,Proc. of the 17th InternationalConference on Computer Aided Verification,Volume 3576 ofLNCS,pages 253-265.施普林格,2005年。
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)