Deciding bisimulation-like equivalences with finite-state processes

被引:0
作者
Jancar, P
Kucera, A
Mayr, R
机构
[1] Tech Univ Ostrava, Dept Comp Sci FEI, CS-70833 Ostrava, Czech Republic
[2] Fac Informat MU, Brno 60200, Czech Republic
[3] Tech Univ Munich, Inst Informat, D-80290 Munich, Germany
来源
AUTOMATA, LANGUAGES AND PROGRAMMING | 1998年 / 1443卷
关键词
D O I
暂无
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We design a general method for proving decidability of bisimulation-like equivalences between infinite-state processes and finite-state ones. We apply this method to the class of PAD processes, which strictly subsumes PA and pushdown (PDA) processes, showing that a large class of bisimulation-like equivalences (including e.g. strong and weak bisimilarity) is decidable between PAD and finite-state processes. On the other hand, we also demonstrate that no 'reasonable' bisimulation-like equivalence is decidable between state-extended PA processes and finite-state ones. Furthermore, weak bisimilarity with finite-state processes is shown to be undecidable even for state-extended BPP (which are also known as 'parallel pushdown processes').
引用
收藏
页码:200 / 211
页数:12
相关论文
共 23 条
  • [1] [Anonymous], 1989, INFORM PROCESSING
  • [2] DECIDABILITY OF BISIMULATION EQUIVALENCE FOR PROCESSES GENERATING CONTEXT-FREE LANGUAGES
    BAETEN, JCM
    BERGSTRA, JA
    KLOP, JW
    [J]. JOURNAL OF THE ACM, 1993, 40 (03) : 653 - 682
  • [3] CERNA I, 1997, ENTCS, P6
  • [4] BISIMULATION EQUIVALENCE IS DECIDABLE FOR ALL CONTEXT-FREE PROCESSES
    CHRISTENSEN, S
    HUTTEL, H
    STIRLING, C
    [J]. INFORMATION AND COMPUTATION, 1995, 121 (02) : 143 - 148
  • [5] Christensen S., 1993, LECTURE NOTES COMPUT, V715, P143
  • [6] ESPARZA J, 1995, LNCS, V965, P221
  • [7] UNDECIDABILITY OF BISIMILARITY FOR PETRI NETS AND SOME RELATED PROBLEMS
    JANCAR, P
    [J]. THEORETICAL COMPUTER SCIENCE, 1995, 148 (02) : 281 - 301
  • [8] JANCAR P, 1996, LECT NOTES COMPUTER, V1099, P478
  • [9] JANCAR P, 1998, TUMI9805
  • [10] JANCAR P, 1997, ENTCS, P9