An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems (Q1097037): Difference between revisions

Vector addition systems (VASs), introduced by \textit{R. M. Karp} and \textit{R. E. Miller} [J. Comput. Syst. Sci. 3, 147-195 (1969; Zbl 0198.326)] are known to be equivalent to Petri nets. For a subclass of VASs called conflict-free VASs an upper bound of exponential time for solving the boundedness problem is given by \textit{L. H. Landweber} and \textit{E. L. Robertson} [J. Assoc. Comput. Mach. 25, 352-264 (1978; Zbl 0384.68062)]. The paper first introduces the notion of conflict-free vector replacement systems (VRSs), that is general enough to include both conflict-free VASs and Petri nets as special cases. Then an \(O(n^{1.5})\) algorithm for determining boundedness of conflict-free VRSs is proved. The proof relies on the assumption that no number in any addition rule is less than -1.