Well-structured transition systems everywhere!

被引：432
|
作者：
Finkel, A
Suhnoebelen, P
机构：
[1] ENS Cachan, Lab Specificat & Verificat, F-94235 Cachan, France
[2] CNRS UMR 8643, F-94235 Cachan, France
来源：
THEORETICAL COMPUTER SCIENCE | 2001年 / 256卷 / 1-2期
关键词：
infinite systems; verification; well-quasi-ordering;
D O I：
10.1016/S0304-3975(00)00102-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Well-structured transition systems (WSTSs) are a general class of infinite-state systems for which decidability results rely on the existence of a well-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 classical systems to be seen as instances of WSTSs. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：63 / 92
页数：30
相关论文
共 50 条
  • [1] Unfolding concurrent well-structured transition systems
    Herbreteau, Frederic
    Sutre, Gregoire
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, PROCEEDINGS, 2007, 4424 : 706 - +
  • [2] Ideal Abstractions for Well-Structured Transition Systems
    Zufferey, Damien
    Wies, Thomas
    Henzinger, Thomas A.
    VERIFICATION, MODEL CHECKING, AND ABSTRACT INTERPRETATION, 2012, 7148 : 445 - 460
  • [3] Ordinal theory for expressiveness of well-structured transition systems
    Bonnet, Remi
    Finkel, Alain
    Haddad, Serge
    Rosa-Velardo, Fernando
    INFORMATION AND COMPUTATION, 2013, 224 : 1 - 22
  • [4] Fundamental structures in well-structured infinite transition systems
    Finkel, A
    Schnoebelen, P
    LATIN '98: THEORETICAL INFORMATICS, 1998, 1380 : 102 - 118
  • [5] Model checking μ-Calculus in well-structured transition systems
    Kouzmin, EV
    Shilov, NV
    Sokolov, VA
    11TH INTERNATIONAL SYMPOSIUM ON TEMPORAL REPRESENTATION AND REASONING, PROCEEDINGS, 2004, : 152 - 155
  • [6] A classification of the expressive power of well-structured transition systems
    Abdulla, Parosh Aziz
    Delzanno, Giorgio
    Van Begin, Laurent
    INFORMATION AND COMPUTATION, 2011, 209 (03) : 248 - 279
  • [7] Handling infinitely branching well-structured transition systems
    Blondin, Michael
    Finkel, Alain
    McKenzie, Pierre
    INFORMATION AND COMPUTATION, 2018, 258 : 28 - 49
  • [8] Comparing the expressive power of well-structured transition systems
    Abdulla, Parosh Aziz
    Delzanno, Giorgio
    Van Begin, Laurent
    COMPUTER SCIENCE LOGIC, PROCEEDINGS, 2007, 4646 : 99 - +
  • [9] Decidability results for well-structured transition systems with auxiliary storage
    Chadha, R.
    Viswanathan, M.
    CONCUR 2007 - CONCURRENCY THEORY, PROCEEDINGS, 2007, 4703 : 136 - +
  • [10] Using well-structured transition systems to decide divergence for catalytic P systems
    Busi, Nadia
    THEORETICAL COMPUTER SCIENCE, 2007, 372 (2-3) : 125 - 135
12345