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 条
  • [11] WELL BEHAVED TRANSITION SYSTEMS
    Blondin, Michael
    Finkel, Alain
    McKenzie, Pierre
    LOGICAL METHODS IN COMPUTER SCIENCE, 2017, 13 (03)
  • [12] WELL (AND BETTER) QUASI-ORDERED TRANSITION SYSTEMS
    Abdulla, Parosh Aziz
    BULLETIN OF SYMBOLIC LOGIC, 2010, 16 (04) : 457 - 515
  • [13] From Featured Transition Systems to Modal Transition Systems with Variability Constraints
    ter Beek, Maurice H.
    Damiani, Ferruccio
    Gnesi, Stefania
    Mazzanti, Franco
    Paolini, Luca
    SOFTWARE ENGINEERING AND FORMAL METHODS, 2015, 9276 : 344 - 359
  • [14] Battery Transition Systems
    Boker, Udi
    Henzinger, Thomas A.
    Radhakrishna, Arjun
    ACM SIGPLAN NOTICES, 2014, 49 (01) : 595 - 606
  • [15] Diagnosability of fair transition systems
    Bittner, Benjamin
    Bozzano, Marco
    Cimatti, Alessandro
    Gario, Marco
    Tonetta, Stefano
    Vozarova, Viktoria
    ARTIFICIAL INTELLIGENCE, 2022, 309
  • [16] When are stochastic transition systems tameable?
    Bertrand, Nathalie
    Bouyer, Patricia
    Brihaye, Thomas
    Carlier, Pierre
    JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING, 2018, 99 : 41 - 96
  • [17] Static Analysis of Featured Transition Systems
    ter Beek, Maurice H.
    Damiani, Ferruccio
    Lienhardt, Michael
    Mazzanti, Franco
    Paolini, Luca
    SPLC'19: PROCEEDINGS OF THE 23RD INTERNATIONAL SYSTEMS AND SOFTWARE PRODUCT LINE CONFERENCE, VOL A, 2020, : 39 - 51
  • [18] On the expressiveness of modal transition systems with variability constraints
    ter Beek, Maurice H.
    Damiani, Ferruccio
    Gnesi, Stefania
    Mazzanti, Franco
    Paolini, Luca
    SCIENCE OF COMPUTER PROGRAMMING, 2019, 169 : 1 - 17
  • [19] AUTOMATIC VERIFICATION OF PROPERTIES IN TRANSITION-SYSTEMS
    ARNOLD, A
    BRLEK, S
    SOFTWARE-PRACTICE & EXPERIENCE, 1995, 25 (06): : 579 - 596
  • [20] Exploring inconsistencies between modal transition systems
    Sassolas, Mathieu
    Chechik, Marsha
    Uchitel, Sebastian
    SOFTWARE AND SYSTEMS MODELING, 2011, 10 (01): : 117 - 142
12345