文章基本信息

标题：Further Results on Partial Order Equivalences on Infinite Systems
本地全文：下载
作者：Kim Sunesen
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1998
卷号：5
期号：6
出版社：Aarhus University
摘要：In [26], we investigated decidability issues for standard language equivalence for process description languages with two generalisations based on traditional approaches for capturing non-interleaving behaviour: pomset equivalence reflecting global causal dependency, and location equivalence reflecting spatial distribution of events. In this paper, we continue by investigating the role played by TCSP-style renaming and hiding combinators with respect to decidability. One result of [26] was that in contrast to pomset equivalence, location equivalence remained decidable for a class of processes consisting of finite sets of BPP processes communicating in a TCSP manner. Here, we show that location equivalence becomes undecidable when either renaming or hiding is added to this class of processes. Furthermore, we investigate the weak versions of location and pomset equivalences. We show that for BPP with prefixing, both weak pomset and weak location equivalence are decidable. Moreover, we show that weak location equivalence is undecidable for BPP semantically extended with CCS communication.