Well-structured transition systems everywhere!

Authors
Finkel, A Suhnoebelen, P
Citation
A. Finkel et P. Suhnoebelen, Well-structured transition systems everywhere!, THEOR COMP, 256(1-2), 2001, pp. 63-92
Citations number
62
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
256
Issue
1-2
Year of publication
2001
Pages
63 - 92
Database
ISI
SICI code
0304-3975(20010406)256:1-2<63:WTSE>2.0.ZU;2-A
Abstract
Well-structured transition systems (WSTSs) are a general class of infinite- state systems for which decidability results rely on the existence of a wel l-quasi-ordering between states that is compatible with the transitions. In this article, we provide an extensive treatment of the WSTS idea and show several new results. Our improved definitions allow many examples of classi cal systems to be seen as instances of WSTSs. (C) 2001 Elsevier Science B.V . All rights reserved.