The covering and boundedness problems for vector addition systems
1978; Elsevier BV; Volume: 6; Issue: 2 Linguagem: Inglês
10.1016/0304-3975(78)90036-1
ISSN1879-2294
Autores Tópico(s)Optimization and Packing Problems
ResumoNew decision procedures for the covering and boundedness problems for vector addition systems are obtained. These procedures require at most space 2cn log n for some constant c. The procedures nearly achieve recently established lower bounds on the amount of space inherently required to solve these problems, and so are much more efficient than previously known non-primitive-recursive decision procedures.
Referência(s)