吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 245-251.doi: 10.13229/j.cnki.jdxbgxb201501036

• Orignal Article • Previous Articles     Next Articles

Lazy slicing based method for verifying linear temporal logic property

HUANG Hong-tao1,WANG Jing2,YE Hai-zhi1,HUANG Shao-bin3   

  1. 1.Engineering Research Center for Education Information, Henan Normal University, Xinxiang 453007, China;
    2.Information Center of Xinxiang Oil Transportation Department, Sinopec Pipeline Storage
    Transportation Company, Xinxiang 453007, China;
    3.College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China
  • Received:2013-05-14 Online:2015-02-01 Published:2015-02-01

Abstract: Lazy slicing is an effective state-space reduction method, but it can not directly determine whether a model satisfies the expected linear property. A lazy slicing based method is proposed to solve this problem. First, it constructs a negation Büchi automaton for given linear temporal logic formula and a product automaton of the system model. Then it searches for an acceptable trace on this product automaton lazily. Thus, the problem of verifying a linear time property is converted into the problem of invariance validation, which makes it possible to search the acceptable state by reachability analysis. Experiment results show that this lazy slicing based algorithm not only makes lazy slicing be able to verify linear time property, but also remarkably improves the scalability of LTL model checking.

CLC Number: 

  • TP311.5
[1] LI Yong, HUANG Zhi-qiu, WANG Yong, FANG Bing-wu. New approach of cross-project defect prediction based on multi-source data [J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[2] WANG Zhi-jian, HU Yu-ping, CHEN Zhang. Describing component based software system architecture using Petri net [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 304-308.
[3] ZHAO Qian, WANG Hui-qiang, FENG Guang-sheng, ZHAO Jing. Measuring method of software dependability based on Pi calculus [J]. 吉林大学学报(工学版), 2011, 41(6): 1684-1689.
[4] WANG Jin-bo, ZHAO Guang-heng, CHEN Wei-wei . Software reliability growth model based on criticality partition of
functional profile for embedded software
[J]. 吉林大学学报(工学版), 2009, 39(02): 436-0439.
[5] Fan Yong-kai,Lin Jun,Sun Tian-ze,Sui Yang-yi . Requirementdriven virtual instrument software automatic generation framework [J]. 吉林大学学报(工学版), 2007, 37(03): 606-0610.
[6] Pan Hong-jun,, Sun Ji-gui. Object oriented algebra Petri net [J]. 吉林大学学报(工学版), 2006, 36(03): 382-0386.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!