On Reachability Equivalence for BPP-Nets.
Journal
Theor. Comput. Sci.
Journal Volume
179
Journal Issue
1-2
Pages
301-317
Date Issued
1997
Author(s)
Abstract
In 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.
Other Subjects
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 nets
Type
journal article