文章基本信息

标题：On Plain and Hereditary History-Preserving Bisimulation
本地全文：下载
作者：Sibylle B. Fröschle ; Thomas Troels Hildebrandt
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：1999
卷号：6
期号：4
出版社：Aarhus University
摘要：We investigate the difference between two well-known notions of independence bisimilarity, history-preserving bisimulation and hereditary history-preserving bisimulation. We characterise the difference between the two bisimulations in trace-theoretical terms, advocating the view that the first is (just) a bisimulation for causality, while the second is a bisimulation for concurrency. We explore the frontier zone between the two notions by defining a hierarchy of bounded backtracking bisimulations. Our goal is to provide a stepping stone for the solution to the intriguing open problem of whether hereditary history-preserving bisimulation is decidable or not. We prove that each of the bounded bisimulations is decidable. However, we also prove that the hierarchy is strict. This rules out the possibility that decidability of the general problem follows directly from the special case. Finally, we give a non- trivial reduction solving the general problem for a restricted class of systems and give pointers towards a full answer.