Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T18:04:02.617Z Has data issue: false hasContentIssue false

Well (and Better) Quasi-Ordered Transition Systems

Published online by Cambridge University Press:  15 January 2014

Parosh Aziz Abdulla*
Affiliation:
Department of Information Technology, Uppsala University, P.O. Box 337, 751 05 Uppsala, Sweden E-mail: parosh@it.uu.se

Abstract

In this paper, we give a step by step introduction to the theory of well quasi-ordered transition systems. The framework combines two concepts, namely (i) transition systems which are monotonic wrt. a well-quasi ordering; and (ii) a scheme for symbolic backward reachability analysis. We describe several models with infinite-state spaces, which can be analyzed within the framework, e.g., Petri nets, lossy channel systems, timed automata, timed Petri nets, and multiset rewriting systems. We will also present better quasi-ordered transition systems which allow the design of efficient symbolic representations of infinite sets of states.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable