|
Well-structured Transition System
In computer science, specifically in the field of formal verification, well-structured transition systems (WSTSs) are a general class of infinite state systems for which many verification problems are decidable language, decidable, owing to the existence of a kind of well-quasi-ordering, order between the states of the system which is compatible with the transitions of the system. WSTS decidability results can be applied to Petri nets, lossy channel systems, and more. Formal definition Recall that a well-quasi-ordering \leq on a set X is a quasi-ordering (i.e., a preorder or reflexive relation, reflexive, transitive relation, transitive binary relation) such that any infinite sequence of elements x_0, x_1, x_2, \ldots, from X contains an increasing pair x_i \leq x_j with i < j. The set is said to be well-quasi-ordered, or shortly wqo. For our purposes, a ''transition system'' is a structure , whe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. Formal verification can be helpful in proving the correctness of systems such as: cryptographic protocols, combinational circuits, digital circuits with internal memory, and software expressed as source code. The verification of these systems is done by providing a formal proof on an abstract mathematical model of the system, the correspondence between the mathematical model and the nature of the system being otherwise known by construction. Examples of mathematical objects often used to model systems are: finite-state machines, labelled transition systems, Petri nets, vector addition systems, timed automata, hybrid automata, process algebra, formal semantics of programming languages such as operational semantics, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
