A multiparameter analysis of the boundedness problem for vector addition systems

DOI10.1016/0022-0000(86)90006-1zbMath0614.68048OpenAlexW2066238373MaRDI QIDQ1819938

Louis E. Rosier, Hsu-Chun Yen

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90006-1

zbMATH Keywords

reachability setvector addition systemscommunicating finite state machinescomplexity of the boundedness problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems, The complexity of reachability in distributed communicating processes, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, Completeness results for conflict-free vector replacement systems, On selective unboundedness of VASS, Nondecreasing subsequences of t-sequences, Small vertex cover makes Petri net coverability and boundedness easier, The complexity of problems involving structurally bounded and conservative Petri nets, A unified approach for deciding the existence of certain petri net paths, Verification of membrane systems with delays via Petri nets with delays, Strategic reasoning with a bounded number of resources: the quest for tractability, A multiparameter analysis of domino tiling with an application to concurrent systems, Strategy synthesis for multi-dimensional quantitative objectives, Partial-Observation Stochastic Games, Communicating processes, scheduling, and the complexity of nontermination, Reachability solution characterization of parametric real-time systems, Unnamed Item, Unnamed Item, On minimal elements of upward-closed sets, A taxonomy of fairness and temporal logic problems for Petri nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unboundedness detection for a class of communicating finite-state machines
• On the reachability problem for 5-dimensional vector addition systems
• Complexity of some problems in Petri nets
• The covering and boundedness problems for vector addition systems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Relationships between nondeterministic and deterministic tape complexities
• Parallel program schemata
• Priority Networks of Communicating Finite State Machines
• Gradually intractable problems and nondeterministic log-space lower bounds
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers