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 条
  • [21] A Structured Validation and Verification Method for Automotive Systems Considering the OEM/Supplier Interface
    Beckers, Kristian
    Cote, Isabelle
    Frese, Thomas
    Hatebur, Denis
    Heisel, Maritta
    COMPUTER SAFETY, RELIABILITY, AND SECURITY, SAFECOMP 2015, 2015, 9337 : 90 - 108
  • [22] Verification of Safety and Liveness Properties of Metric Transition Systems
    Girard, Antoine
    Zheng, Gang
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2012, 11
  • [23] Verification of infinite-state dynamic systems using approximate quotient transition systems
    Chutinan, A
    Krogh, BH
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2001, 46 (09) : 1401 - 1410
  • [24] Partial Model Checking Using Networks of Labelled Transition Systems and Boolean Equation Systems
    Lang, Frederic
    Mateescu, Radu
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, TACAS 2012, 2012, 7214 : 141 - 156
  • [25] Computing Augmented Finite Transition Systems to Synthesize Switching Protocols for Polynomial Switched Systems
    Ozay, Necmiye
    Liu, Jun
    Prabhakar, Pavithra
    Murray, Richard M.
    2013 AMERICAN CONTROL CONFERENCE (ACC), 2013, : 6237 - 6244
  • [26] Rapid development of structured simulation models for the verification of discrete-event control systems
    Sanchez, A
    Gollain, C
    Macchietto, S
    DYNAMICS & CONTROL OF PROCESS SYSTEMS 1998, VOLUMES 1 AND 2, 1999, : 625 - 630
  • [27] Computing meta-transitions for linear transition systems with polynomials
    Musset, J
    Rusinowitch, M
    FME 2003: FORMAL METHODS, PROCEEDINGS, 2003, 2805 : 562 - 581
  • [28] Opacity of Nondeterministic Transition Systems: A (Bi)Simulation Relation Approach
    Zhang, Kuize
    Yin, Xiang
    Zamani, Majid
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2019, 64 (12) : 5116 - 5123
  • [29] A Deductive Approach towards Reasoning about Algebraic Transition Systems
    Fu, Jun
    Wu, Jinzhao
    Tan, Hongyan
    MATHEMATICAL PROBLEMS IN ENGINEERING, 2015, 2015
  • [30] Logical characterization of branching metrics for nondeterministic probabilistic transition systems
    Castiglioni, Valentina
    Tini, Simone
    INFORMATION AND COMPUTATION, 2019, 268
12345