REDUCTION AND COVERING OF INFINITE REACHABILITY TREES

被引：51
作者：
FINKEL, A
机构：
[1] RES CTR COMP SCI MONTREAL, MONTREAL, QUEBEC, CANADA
[2] UNIV MONTREAL, MONTREAL H3C 3J7, QUEBEC, CANADA
来源：
INFORMATION AND COMPUTATION | 1990年 / 89卷 / 02期
关键词：
D O I：
10.1016/0890-5401(90)90009-7
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a structure for transition systems with which the main decidability results on Petri nets can be generalized to structured transition systems. We define the reduced reachability tree of a structured transition system; it allows one to decide the finite reachability tree problem (also called the finite termination problem) and the finite reachability set problem. A general definition of the coverability set is given and the procedure of Karp and Miller is extended for well-structured transition systems. We show then that the coverability problem is a decidable problem in the framework of well-structured transition systems. Finally, we introduce structured set of terminal states and we show that the finite reachability tree problem and the finite reachability set problem are decidable. Coverability is an open problem for structured transition systems with a structured set of terminal states. © 1990.
引用
收藏
页码：144 / 179
页数：36
相关论文
共 33 条
  • [1] Birkhoff G., 1979, LATTICE THEORY, V25
  • [2] BOCHMAN G, 1978, FEB P COMP NETW PROT, P361
  • [3] BOCHMANN G, 1988, 650 U MONTR INT REP
  • [4] BOCHMANN G, 1988, 2ND INT S INT INF SY
  • [5] BRAMS GW, 1983, RESEAUX PETRI THEORI, V1
  • [6] ON COMMUNICATING FINITE-STATE MACHINES
    BRAND, D
    ZAFIROPULO, P
    [J]. JOURNAL OF THE ACM, 1983, 30 (02) : 323 - 342
  • [7] BRAUER W, 1986, LECTURE NOTES COMPUT, V255
  • [8] CHOQUET A, 1987, 8TH EUR WORKSH APPL
  • [9] CHOQUET A, 1987, THESIS U PARIS 11
  • [10] FINKEL A, 1988, 8TH INT S PROT SPEC
1234