Reachability in vector-addition systems

Prelegent(ci)

Mikolaj Bojanczyk

Afiliacja

Uniwersytet Warszawski

Termin

29 marca 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---