Abstract
With geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory but unsolved ever since it was proposed by Karp and Miller. We show that the reachability-problem is decidable in dim. ≤ 3 and give a partial solution for the general problem covering a wide instance of it. In both cases a semi-linear characterization is obtained for the complete set of solutions. Contrary to common belief the complete solution in dim. 3 does not immediately generalize, and our analysis gives evidence why. A few generalizations and application to long-standing classificational problems in language theory are discussed.
Keywords
ReachabilityReachability problemDecidabilityCharacterization (materials science)Set (abstract data type)Computer scienceMathematicsAlgebra over a fieldTheoretical computer scienceDiscrete mathematicsPure mathematicsProgramming language
Affiliated Institutions
Related Publications
A general approach for developing system‐specific functions to score protein–ligand docked complexes using support vector inductive logic programming
Abstract Despite the increased recent use of protein–ligand and protein–protein docking in the drug discovery process due to the increases in computational power, the difficulty...
Fast Training of Support Vector Machines Using Sequential Minimal Optimization
This chapter describes a new algorithm for training Support Vector Machines: Sequential Minimal Optimization, or SMO. Training a Support Vector Machine (SVM) requires the soluti...
The Approximation of One Matrix by Another of Lower Rank
The mathematical problem of approximating one matrix by another of lower rank is closely related to the fundamental postulate of factor-theory. When formulated as a least-square...
Scattered Data Approximation
Many practical applications require the reconstruction of a multivariate function from discrete, unstructured data. This book gives a self-contained, complete introduction into ...
Genetic Programming: On the Programming of Computers by Means of Natural Selection
Background on genetic algorithms, LISP, and genetic programming hierarchical problem-solving introduction to automatically-defined functions - the two-boxes problem problems tha...
Publication Info
- Year
- 1974
- Type
- article
- Pages
- 303-309
- Citations
- 47
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
47
OpenAlex
Cite This
Jan Van Leeuwen
(1974).
A partial solution to the reachability-problem for vector-addition systems.
, 303-309.
https://doi.org/10.1145/800119.803908
Identifiers
- DOI
- 10.1145/800119.803908