Fröschle, Sibylle B.Sibylle B.Fröschle2021-12-202021-12-201999-12-01Electronic Notes in Theoretical Computer Science 27: 85-106 (1999-12-01)http://hdl.handle.net/11420/11327In this paper we investigate the decidability of history-preserving bisimilarity (HPB) and hereditary history-preserving bisimilarity (HHPB) for basic parallel processes (BPP). We find that both notions are decidable for this class of infinite systems, and present tableau-based decision procedures. The first result is not new but has already been established via the decidability of causal bisimilarity, a notion that is equivalent to HPB. We shall see that our decision procedure is similar to Christensen's proof of the decidability of distributed bisimilarity, which leads us to the coincidence between HPB and distributed bisimilarity for B-The decidability of HHPB is a new result. This result is especially interesting, since the decidability of HHPB for finite-state systems has been a long-standing open problem which has recently been shown to be undecidable. I would like to thank the many people with whom I have discussed the notions of plain and hereditary HPB, in particular I thank Colin Stirling for his advice on my BPP work, Astrid Kiehn for providing me with her notes on distributed bisimilarity, and Ilaria Castellani and Rob van Glabbeek for their helpful comments at EXPRESS. I also thank two of the anonymous referees for valuable comments which drew my attention to the coincidence of distributed and history-preserving bisimilarity.en1571-0661199985106Elsevier Sciencehttps://creativecommons.org/licenses/by-nc-nd/3.0/InformatikConference Paper10.15480/882.404810.1016/S1571-0661(05)80297-X10.15480/882.4048Conference Paper