Temporal Logic, Hardware Verification, and Automatic Theorem Proving
Temporal Logic, Hardware Verification, and Automatic Theorem Proving
批准号:
8722633
负责人:
Edmund Clarke
金额:
$15.84万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1988
资助国家:
美国
项目状态:
已结题
起止时间:
1988-03-01 至 1990-08-31
中文摘要
本工作包括程序逻辑和程序验证两个方面的研究项目。所有的项目都旨在提供工具,使自动验证在更广泛的程序类别中是可行的。前三个项目涉及一种验证有限状态并发系统的方法,称为时间逻辑模型检查。该程序将通过系统地搜索并发系统生成的全局状态图来确定有限状态并发系统是否满足命题时间逻辑中的规范。它已被成功地用于发现已发表的复杂的自定时电路设计中的细微错误。第一个项目是开发处理这种验证可能出现的状态爆炸问题的方法。另一个项目是扩展时间逻辑及其验证程序,以允许在无限磁带上由自动机定义的操作符。这具有实际重要性,因为对时间逻辑的经常批评是它与自动机相比的表达能力。第三个项目涉及实际使用模型检查技术来自动验证硬件控制器。在这种情况下的主要问题是开发在现实时序模型下从电路中提取状态机的方法。最后一个项目是开发一个并行分辨率定理证明器,运行在sequential和Encore多处理器上。它已经在顺利进行。由于主要关注由并发性引起的问题,因此可以使用基于线性解析/模型消除的相当简单的定理证明策略。子句是根据允许并行插入和删除的堆数据结构中的一些启发式函数来维护的。完整系统的原型实现将在未来几个月内运行。接下来将进行其他组织定理证明者的方法和更复杂的定理证明策略的实验。
英文摘要
This work comprises several research projects in logics of programs and program verification. All of the projects are directed towards providing tools that will make automatic verification feasible for a wider class of programs. The first three projects involve an approach to verifying finite state concurrent systems called temporal logic model checking. This procedure will determine if a finite-state concurrent system satisfies its specification in a propositional temporal logic by methodically searching the global state graph generated by the concurrent system. It has been used successfully to find subtle errors in published designs of tricky self-timed circuits. The first project is to develop ways of handling the state explosion problem that may occur with this type of verification. Another project is to extend the temporal logic and its verification procedure to allow operators defined by automata on infinite tapes. This is of practical importance since a frequent criticism of temporal logic is its expressive power compared to automata. The third project involves actually using model checking techniques for the automatic verification of hardware controllers. The main problem in this case is to develop methods of extracting state machines from circuits under realistic timing models. The last project is the development of a parallel resolution theorem prover to run on Sequent and Encore multiprocessors. It is already well underway. Since interest primarily in problems caused by concurrency, one can use a fairly simple theorem proving strategy based on linear resolution/model elimination. Clauses are maintained according to some heuristic function in a heap data structure that permits parallel inserts and deletions. A prototype implementation of the full system should be running in the next few months. Experiments with other ways of organizing the theorem prover and with more complicated theorem proving strategies will follow.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Collaborative Research: Next-Generation Model Checking and Abstract Interpretation with a Focus on Embedded Control and Systems Biology
-
批准号:0926181
-
项目类别:Standard Grant
-
资助金额:$384.57万
-
财政年份:2009
-
负责人:Edmund Clarke
-
依托单位:
The Component Substitution Problem for Software Systems
-
批准号:0541245
-
项目类别:Standard Grant
-
资助金额:$34.83万
-
财政年份:2006
-
负责人:Edmund Clarke
-
依托单位:
EHS: Graph-Based Refinement Strategies for Hybrid Systems
-
批准号:0411152
-
项目类别:Continuing Grant
-
资助金额:$55.0万
-
财政年份:2004
-
负责人:Edmund Clarke
-
依托单位:
Efficient Model Checking of Concurrent and Dynamic Software
-
批准号:0429120
-
项目类别:Continuing Grant
-
资助金额:$0.0万
-
财政年份:2004
-
负责人:Edmund Clarke
-
依托单位:
The CUE Initiative on The Scientific Foundation of Software Engineering
-
批准号:0327252
-
项目类别:Standard Grant
-
资助金额:$0.7万
-
财政年份:2003
-
负责人:Edmund Clarke
-
依托单位:
Automatic Verification of Concurrent Hardware and Software Systems
-
批准号:0098072
-
项目类别:Continuing Grant
-
资助金额:$37.5万
-
财政年份:2001
-
负责人:Edmund Clarke
-
依托单位:
ITR/SY: Verification Tools for Autonomous and Embedded Systems
-
批准号:0121547
-
项目类别:Continuing Grant
-
资助金额:$100.0万
-
财政年份:2001
-
负责人:Edmund Clarke
-
依托单位:
NSF-CNPq Collaborative Research: Formal Verification of Computer Systems in Industrial Complexity
-
批准号:9900309
-
项目类别:Standard Grant
-
资助金额:$15.54万
-
财政年份:1999
-
负责人:Edmund Clarke
-
依托单位:
Automatic Verification of Finite-State Concurrent Systems in Hardware and Software
-
批准号:9803774
-
项目类别:Continuing Grant
-
资助金额:$47.5万
-
财政年份:1998
-
负责人:Edmund Clarke
-
依托单位:
Automatic Verification of Finite-State Concurrent Systems in Hardware and Software
-
批准号:9217549
-
项目类别:Continuing Grant
-
资助金额:$74.49万
-
财政年份:1993
-
负责人:Edmund Clarke
-
依托单位:
U.S.-Japan Cooperative Research: Formal Verification of Finite State Systems
-
批准号:9016694
-
项目类别:Standard Grant
-
资助金额:$1.98万
-
财政年份:1991
-
负责人:Edmund Clarke
-
依托单位:
Temporal Logic, Hardware Verification, and Parallel Theorem Proving
-
批准号:9005992
-
项目类别:Continuing Grant
-
资助金额:$21.2万
-
财政年份:1990
-
负责人:Edmund Clarke
-
依托单位:
Programming Language Issues in VLSI Design
-
批准号:8509909
-
项目类别:Continuing Grant
-
资助金额:$17.75万
-
财政年份:1986
-
负责人:Edmund Clarke
-
依托单位:
Workshop on Logics of Programs, Pittsburgh, Pennsylvania, June 5-8, 1983
-
批准号:8303082
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:1983
-
负责人:Edmund Clarke
-
依托单位:
Design and Verification of Concurrent Systems (Computer Research)
-
批准号:8216706
-
项目类别:Standard Grant
-
资助金额:$22.14万
-
财政年份:1982
-
负责人:Edmund Clarke
-
依托单位:
Design and Verification of Concurrent Systems
-
批准号:8105553
-
项目类别:Standard Grant
-
资助金额:$12.73万
-
财政年份:1981
-
负责人:Edmund Clarke
-
依托单位:
Verification of Recursive Programs, Concurrent Programs, AndAbstract Data Types
-
批准号:7908365
-
项目类别:Standard Grant
-
资助金额:$5.72万
-
财政年份:1979
-
负责人:Edmund Clarke
-
依托单位:
国内基金
海外基金
greenwashing behavior in China:Basedon an integrated view of reconfiguration of environmental authority and decoupling logic
-
批准号:--
-
项目类别:外国学者研究基金项目
-
资助金额:--
-
批准年份:2024
-
负责人:YU BYUNGJUN
-
依托单位:
Incentive and governance schenism study of corporate green washing behavior in China: Based on an integiated view of econfiguration of environmental authority and decoupling logic
-
批准号:--
-
项目类别:外国学者研究基金项目
-
资助金额:--
-
批准年份:2024
-
负责人:YU BYUNGJUN
-
依托单位: