HSU-CHUN YEN2020-06-162020-06-161997https://www.scopus.com/inward/record.uri?eid=2-s2.0-0031166423&doi=10.1016%2fs0304-3975%2896%2900147-8&partnerID=40&md5=60306575a220c04fe9d22fde424d11b3In this paper, we study the complexity of the reachability equivalence problem for BPP-nets. BPP-nets are closely related to Basic Parallel Processes, which form a subclass of Milner's CCS. We show the reachability equivalence problem for BPP-nets to be solvable in DTIME(22ds3), where d is a constant and s is the size of the problem instance, when a standard binary encoding scheme is used. To that end, we provide a new characterization for computations in BPP-nets, which, in turn, facilitates the derivation of small semilinear set representations for the reachability sets of BPP-nets. As for the lower bound, the problem is shown to be Π2P-hard. Our results improve upon the previous decidability result of the reachability equivalence problem for BPP-nets.Binary codes; Computability and decidability; Computational complexity; Computational linguistics; Computational methods; Equivalence classes; Parallel processing systems; Problem solving; Basic parallel processes nets (BPP-nets); Reachability equivalence; Petri netsjournal article10.1016/S0304-3975(96)00147-82-s2.0-0031166423https://doi.org/10.1016/S0304-3975(96)00147-8