Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
type: Item
instance of: scholarly article
title: Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
zbMATH Open document ID: 0633.68029
DOI: 10.1016/0304-3975(86)90026-5
author: Rodney R. Howell
author: Louis E. Rosier
author: Dung T. Huynh
author: Hsu-Chun Yen
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: The containment and equivalence problems for vector addition systems (VASs) (or equivalently, vector addition systems with states (VASSs) or Petri nets) are, in general, undecidable. They are decidable, however, for classes of VASs (VASSs, Petri nets) whose reachability sets are effectively computable semilinear sets (SLSs). The authors analyse the complexity of the reachability, containment, and equivalence problems for two classes of VASSs. Both of these classes are known to have effectively computable SLSs. By giving upper bounds on the sizes of the SLS representations, they achieve upper bounds on each of the mentioned problems. The techniques they use in deriving their upper bounds represent an original approach to the problem. These techniques may have applications to other problems.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q85
zbMATH DE Number: 4030974
zbMATH Keywords: decidability
zbMATH Keywords: complexity analysis
zbMATH Keywords: equivalence problems
zbMATH Keywords: vector addition systems
zbMATH Keywords: Petri nets
zbMATH Keywords: reachability sets
zbMATH Keywords: effectively computable semilinear sets
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90026-5
OpenAlex ID: W2001068306
cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations
cites work: Alternation
cites work: On the finite containment problem for Petri nets
cites work: Q4152749
cites work: A decidability theorem for a class of vector-addition systems
cites work: Q4115143
cites work: The decidability of persistence for vector addition systems
cites work: Vector addition systems and regular languages
cites work: The equality problem for vector addition systems is undecidable
cites work: On the reachability problem for 5-dimensional vector addition systems
cites work: Q3668872
cites work: Complexity of the word problem for commutative semigroups of fixed dimension
cites work: The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
cites work: Q4727433
cites work: A note on the complexity of program evaluation
cites work: Parallel program schemata
cites work: Properties of Conflict-Free and Persistent Petri Nets
cites work: Persistence of vector replacement systems is decidable
cites work: An Algorithm for the General Petri Net Reachability Problem
cites work: Petri nets and large finite sets
cites work: The Complexity of the Finite Containment Problem for Petri Nets
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Q3891773
cites work: A multiparameter analysis of the boundedness problem for vector addition systems
cites work: Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines
cites work: Q3746869
cites work: Q5603731
cites work: Q4136592
cites work: Petri nets and regular languages
cites work: On weak persistency of Petri nets
description: scientific article; zbMATH DE number 4030974