You are not logged in | Log in

Reachability in vector-addition systems

Mikolaj Bojanczyk
Uniwersytet Warszawski
March 29, 2006, 2:15 p.m.
room 5870
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.