59:
96:. An initial vector is seen as the initial values of multiple counters, and the vectors of the VAS are seen as updates. These counters may never drop below zero. More precisely, given an initial vector with non negative values, the vectors of the VAS can be added componentwise, given that every intermediate vector has non negative values. A
273:
567:
344:
158:
694:
476:
379:
653:
605:
184:
435:
299:
511:
226:
405:
62:
Example of a vector addition with states. In this VASS, e.g., q(1,2) can be reached from p(0,0), but q(0,0) cannot be reached from p(0,0).
892:
882:
231:
789:
Hopcroft, John E.; Pansiot, Jean-Jacques (1979). "On the reachability problem for 5-dimensional vector addition systems".
907:
716:
519:
314:
128:
887:
658:
440:
349:
614:
105:
112:
vectors. VASS have the same restriction that the counter values should never drop below zero.
721:
572:
163:
74:
414:
278:
711:
484:
199:
66:
8:
902:
384:
28:
856:
831:
70:
774:
757:
897:
802:
806:
798:
769:
726:
47:
and Jean-Jacques
Pansiot in 1979. Both VAS and VASS are equivalent in many ways to
52:
32:
194:
101:
58:
876:
855:. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS).
830:. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS).
44:
736:
27:) is one of several mathematical modeling languages for the description of
731:
100:
is a VAS equipped with control states. More precisely, it is a finite
93:
811:
706:
48:
861:
836:
853:
The
Reachability Problem for Petri Nets is Not Primitive Recursive
109:
90:
828:
Reachability in Vector
Addition Systems is Ackermann-complete
268:{\displaystyle T\subseteq Q\times \mathbb {Z} ^{d}\times Q}
115:
661:
617:
575:
522:
487:
443:
417:
387:
352:
317:
281:
234:
202:
166:
131:
825:
688:
647:
599:
561:
505:
470:
429:
399:
373:
338:
293:
267:
220:
178:
152:
35:and Raymond E. Miller in 1969, and generalized to
826:CzerwiĆski, Wojciech; Orlikowski, Ćukasz (2021).
756:Karp, Richard M.; Miller, Raymond E. (May 1969).
562:{\displaystyle (p,u)\in Q\times \mathbb {N} ^{d}}
874:
788:
31:. Vector addition systems were introduced by
339:{\displaystyle V\subseteq \mathbb {Z} ^{d}}
153:{\displaystyle V\subseteq \mathbb {Z} ^{d}}
755:
860:
835:
810:
773:
676:
549:
458:
361:
326:
249:
140:
116:Formal definitions and basic terminology
57:
762:Journal of Computer and System Sciences
689:{\displaystyle u+v\in \mathbb {N} ^{d}}
471:{\displaystyle u+v\in \mathbb {N} ^{d}}
875:
850:
80:
374:{\displaystyle u\in \mathbb {N} ^{d}}
37:vector addition systems with states
13:
717:Communicating finite-state machine
98:vector addition system with states
14:
919:
893:Concurrency (computer science)
883:Formal specification languages
844:
819:
782:
749:
636:
618:
594:
576:
535:
523:
500:
488:
305:
215:
203:
69:in vector addition systems is
16:Mathematical modeling language
1:
775:10.1016/S0022-0000(69)80011-5
742:
803:10.1016/0304-3975(79)90041-0
791:Theoretical Computer Science
648:{\displaystyle (p,v,q)\in T}
89:consists of a finite set of
7:
758:"Parallel program schemata"
700:
10:
924:
908:Software modeling language
346:be a VAS. Given a vector
611:, in one transition, if
411:, in one transition, if
851:Leroux, JĂ©rĂŽme (2021).
600:{\displaystyle (q,u+v)}
179:{\displaystyle d\geq 1}
690:
649:
601:
563:
507:
472:
431:
430:{\displaystyle v\in V}
401:
375:
340:
295:
294:{\displaystyle d>0}
269:
222:
180:
154:
87:vector addition system
63:
51:introduced earlier by
21:vector addition system
888:Models of computation
722:Kahn process networks
691:
650:
602:
564:
508:
506:{\displaystyle (Q,T)}
473:
432:
402:
376:
341:
296:
270:
223:
221:{\displaystyle (Q,T)}
181:
155:
73:-complete (and hence
61:
712:Finite state machine
659:
615:
573:
569:, the configuration
520:
485:
441:
415:
385:
350:
315:
279:
232:
200:
164:
129:
513:be a VASS. Given a
400:{\displaystyle u+v}
81:Informal definition
29:distributed systems
686:
645:
597:
559:
503:
468:
427:
397:
371:
336:
291:
265:
218:
176:
150:
64:
915:
867:
866:
864:
848:
842:
841:
839:
823:
817:
816:
814:
786:
780:
779:
777:
753:
727:Process calculus
695:
693:
692:
687:
685:
684:
679:
654:
652:
651:
646:
606:
604:
603:
598:
568:
566:
565:
560:
558:
557:
552:
512:
510:
509:
504:
477:
475:
474:
469:
467:
466:
461:
436:
434:
433:
428:
406:
404:
403:
398:
380:
378:
377:
372:
370:
369:
364:
345:
343:
342:
337:
335:
334:
329:
300:
298:
297:
292:
274:
272:
271:
266:
258:
257:
252:
227:
225:
224:
219:
185:
183:
182:
177:
159:
157:
156:
151:
149:
148:
143:
125:is a finite set
45:John E. Hopcroft
923:
922:
918:
917:
916:
914:
913:
912:
873:
872:
871:
870:
849:
845:
824:
820:
787:
783:
754:
750:
745:
703:
680:
675:
674:
660:
657:
656:
616:
613:
612:
574:
571:
570:
553:
548:
547:
521:
518:
517:
486:
483:
482:
462:
457:
456:
442:
439:
438:
416:
413:
412:
386:
383:
382:
365:
360:
359:
351:
348:
347:
330:
325:
324:
316:
313:
312:
308:
280:
277:
276:
253:
248:
247:
233:
230:
229:
201:
198:
197:
165:
162:
161:
144:
139:
138:
130:
127:
126:
118:
83:
53:Carl Adam Petri
33:Richard M. Karp
17:
12:
11:
5:
921:
911:
910:
905:
900:
895:
890:
885:
869:
868:
843:
818:
797:(2): 135â159.
781:
768:(2): 147â195.
747:
746:
744:
741:
740:
739:
734:
729:
724:
719:
714:
709:
702:
699:
698:
697:
683:
678:
673:
670:
667:
664:
644:
641:
638:
635:
632:
629:
626:
623:
620:
596:
593:
590:
587:
584:
581:
578:
556:
551:
546:
543:
540:
537:
534:
531:
528:
525:
502:
499:
496:
493:
490:
479:
465:
460:
455:
452:
449:
446:
426:
423:
420:
396:
393:
390:
368:
363:
358:
355:
333:
328:
323:
320:
307:
304:
303:
302:
290:
287:
284:
264:
261:
256:
251:
246:
243:
240:
237:
217:
214:
211:
208:
205:
195:directed graph
187:
175:
172:
169:
147:
142:
137:
134:
117:
114:
102:directed graph
82:
79:
15:
9:
6:
4:
3:
2:
920:
909:
906:
904:
901:
899:
896:
894:
891:
889:
886:
884:
881:
880:
878:
863:
858:
854:
847:
838:
833:
829:
822:
813:
808:
804:
800:
796:
792:
785:
776:
771:
767:
763:
759:
752:
748:
738:
735:
733:
730:
728:
725:
723:
720:
718:
715:
713:
710:
708:
705:
704:
681:
671:
668:
665:
662:
642:
639:
633:
630:
627:
624:
621:
610:
591:
588:
585:
582:
579:
554:
544:
541:
538:
532:
529:
526:
516:
515:configuration
497:
494:
491:
480:
463:
453:
450:
447:
444:
424:
421:
418:
410:
394:
391:
388:
381:, the vector
366:
356:
353:
331:
321:
318:
310:
309:
288:
285:
282:
262:
259:
254:
244:
241:
238:
235:
212:
209:
206:
196:
192:
188:
173:
170:
167:
145:
135:
132:
124:
120:
119:
113:
111:
107:
103:
99:
95:
92:
88:
78:
76:
75:nonelementary
72:
68:
60:
56:
54:
50:
46:
42:
38:
34:
30:
26:
22:
852:
846:
827:
821:
794:
790:
784:
765:
761:
751:
737:Trace theory
608:
514:
408:
193:is a finite
190:
122:
108:labelled by
97:
86:
84:
67:Reachability
65:
40:
36:
24:
20:
18:
732:Actor model
306:Transitions
903:Petri nets
877:Categories
862:2104.12695
837:2104.13866
743:References
228:such that
49:Petri nets
812:1813/6102
707:Petri net
672:∈
640:∈
545:×
539:∈
454:∈
422:∈
357:∈
322:⊆
275:for some
260:×
245:×
239:⊆
171:≥
160:for some
136:⊆
71:Ackermann
898:Diagrams
701:See also
609:reached
607:can be
409:reached
407:can be
110:integer
94:vectors
91:integer
857:arXiv
832:arXiv
104:with
43:) by
655:and
481:Let
437:and
311:Let
286:>
191:VASS
106:arcs
41:VASS
807:hdl
799:doi
770:doi
123:VAS
77:).
25:VAS
879::
805:.
793:.
764:.
760:.
189:A
121:A
85:A
55:.
19:A
865:.
859::
840:.
834::
815:.
809::
801::
795:8
778:.
772::
766:3
696:.
682:d
677:N
669:v
666:+
663:u
643:T
637:)
634:q
631:,
628:v
625:,
622:p
619:(
595:)
592:v
589:+
586:u
583:,
580:q
577:(
555:d
550:N
542:Q
536:)
533:u
530:,
527:p
524:(
501:)
498:T
495:,
492:Q
489:(
478:.
464:d
459:N
451:v
448:+
445:u
425:V
419:v
395:v
392:+
389:u
367:d
362:N
354:u
332:d
327:Z
319:V
301:.
289:0
283:d
263:Q
255:d
250:Z
242:Q
236:T
216:)
213:T
210:,
207:Q
204:(
186:.
174:1
168:d
146:d
141:Z
133:V
39:(
23:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
