自动多项式正式验证使用通用二进制决策图的模式
Martha Schnieber1, Rolf Drechsler1,2
1Institute of Computer Science, University of Bremen, Bremen, Germany.
概括
多项式正式验证 (PFV) 通过使用二进制决策图 (BDD) 来自动证明电路正确性. 这项研究正式化了BDD模式,并开发了用于自动证明生成的算法,使更复杂的函数能够有效地进行验证.
科学领域:
- 计算机科学 计算机科学
- 电气工程 电气工程
- 正式方法 正式方法
背景情况:
- 数字电路无处不在,但容易发生故障,需要强大的验证方法.
- 模拟缺乏完全正确性的保证,而传统的正式验证面临复杂性挑战.
- 多项式正式验证 (PFV) 在多项式时间和空间中提供高效的电路验证.
研究的目的:
- 为了正式化现有的二进制决策图 (BDD) 模式,用于自动化PFV.
- 提出用于检测这些BDD模式的算法.
- 为了使越来越复杂的数字功能能够自动生成证明.
主要方法:
- 对BDD模式的正式化.
- 模式检测算法的开发.
- 基于已识别的模式来产生诱导性证明.
主要成果:
- 为自动化PFV建立了正式的BDD模式.
- 为高效的BDD模式检测提出的算法.
- 证明了复杂函数的示例自动化证明生成.
结论:
- 正式化的模式和检测算法增强了自动化的PFV功能.
- 这项工作扩大了通过自动化PFV可验证的功能范围.
- 进步有助于开发安全的计算平台.
更多相关视频
11:09RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
Published on: July 17, 2021
2.9K
07:16Author Spotlight: Development of a Novel Finite Element Analysis Model for Improved Orthognathic Surgical Techniques
Published on: October 20, 2023
1.2K
相关概念视频
Block Diagram Reduction
155
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
155
Signal Flow Graphs
173
Signal-flow graphs offer a streamlined and intuitive approach to representing control systems, providing an alternative to traditional block diagrams. These graphs use branches to symbolize systems and nodes to represent signals, effectively illustrating the relationships and interactions within the system.
In a signal-flow graph, branches denote the system's transfer functions, while nodes represent the signals. The direction of signal flow is indicated by arrows, with the corresponding...
In a signal-flow graph, branches denote the system's transfer functions, while nodes represent the signals. The direction of signal flow is indicated by arrows, with the corresponding...
173
Elements of Block Diagrams
239
Block diagrams serve as a visual representation of the input-output relationships within a system. An illustrative example is a heating system, where the set temperature activates the furnace to warm the room to the desired level. Block diagrams are versatile, modeling linear systems through Laplace transform variables and nonlinear systems using time domain variables.
A block diagram typically includes essential elements such as comparators, blocks, and feedback loops. Each of these elements...
A block diagram typically includes essential elements such as comparators, blocks, and feedback loops. Each of these elements...
239
Relation between Mathematical Equations and Block Diagrams
166
In a spring-mass-damper system, the second-order differential equation describes the dynamic behavior of the system. When transformed into the Laplace domain under zero initial conditions, this equation can be effectively analyzed and manipulated. The transformation into the Laplace domain converts differential equations into algebraic equations, simplifying the process of isolating the output.
166
SFG Algebra
107
In Signal Flow Graph (SFG) algebra, the value a node represents is determined by the sum of all signals entering that node. This summed value is then transmitted through every branch leaving the node, making the SFG a powerful tool for visualizing and analyzing control systems.
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...
107
Routh-Hurwitz Criterion II
180
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
180
