# Reachability in vector-addition systems

- Speaker(s)
**Mikolaj Bojanczyk**- Affiliation
- Uniwersytet Warszawski
- Date
- March 29, 2006, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory

An (n-dimensional) vector addition system is a finite set V of n-dimensional integer vectors. The reachability problem is as follows: given V and two n-dimensional vectors of *naturals * v and w, determine if one can produce a sequence v=v(1),v(2),..,v(k)=w of vectors of naturals, such that each difference v(i+1) - v(i) -- which need not be a vector of naturals -- belongs to the set V. I will try to describe Kosaraju's algorithm, which solves this problem.