Computer Science – Logic in Computer Science
Scientific paper
2004-09-26
Computer Science
Logic in Computer Science
30 pages, 6 figures
Scientific paper
Many existing algorithms for model checking of infinite-state systems operate on constraints which are used to represent (potentially infinite) sets of states. A general powerful technique which can be employed for proving termination of these algorithms is that of well quasi-orderings. Several methodologies have been proposed for derivation of new well quasi-ordered constraint systems. However, many of these constraint systems suffer from a "constraint explosion problem", as the number of the generated constraints grows exponentially with the size of the problem. In this paper, we demonstrate that a refinement of the theory of well quasi-orderings, called the theory of better quasi-orderings, is more appropriate for symbolic model checking, since it allows inventing constraint systems which are both well quasi-ordered and compact. As a main application, we introduce existential zones, a constraint system for verification of systems with unboundedly many clocks and use our methodology to prove that existential zones are better quasi-ordered. We show how to use existential zones in verification of timed Petri nets and present some experimental results. Also, we apply our methodology to derive new constraint systems for verification of broadcast protocols, lossy channel systems, and integral relational automata. The new constraint systems are exponentially more succinct than existing ones, and their well quasi-ordering cannot be shown by previous methods in the literature.
Abdulla Parosh Aziz
Nylen Aletta
No associations
LandOfFree
Better Quasi-Ordered Transition Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Better Quasi-Ordered Transition Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Better Quasi-Ordered Transition Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-447727