  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.
