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.

---