Jian, Shi-TsuenShi-TsuenJianLao, Ta-PangTa-PangLaoHSU-CHUN YEN2020-06-162020-06-161996https://www.scopus.com/inward/record.uri?eid=2-s2.0-0346614646&doi=10.1016%2fs0304-3975%2896%2980714-6&partnerID=40&md5=8c2140be6f97d03abbba14477a20e8f0In the study of process semantics, trace equivalence and bisimulation equivalence constitute the two extremes of the so-called linear time - branching time spectrum. In this paper, we study the complexity and decidability issues of deciding trace and bisimulation equivalences for the model of systems with many identical processes with respect to various interprocess communication structures. In our model, each system consists of an arbitrary number of identical finite-state processes using Milner's calculus of communicating systems (CCS) as the style of interprocess communication. As it turns out, deciding trace and bisimulation equivalences are undecidable for star-like and linear systems, whereas the two problems are complete for PSPACE and PTIME, respectively, for fully connected systems.Computational complexity; Computer simulation; Finite automata; Mathematical models; Bisimulation equivalences; Calculus of communicating systems (CCS); Interprocess communication structures; Linear time branching time spectrum; Software package PSPACE; Software package PTIME; Trace equivalence; Computability and decidabilityjournal article10.1016/S0304-3975(96)80714-62-s2.0-0346614646https://doi.org/10.1016/S0304-3975(96)80714-6