Geometrically 2-Dimensional Vector Addition System with States

Prelegent(ci)

Yangluo Zheng

Afiliacja

Shanghai Jiao Tong University

Język referatu

angielski

Termin

29 października 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Geometrically 2-Dimensional Vector Addition System with States

Seminarium

Seminarium „Teoria automatów”

---

In the line of work addressing the reachability problem of VASS, the concept of geometrical dimension (the dimension of the vector space spanned by simple cycle effects) was found important to complexity analysis. It is reasonable to study the reachability problem under fixed geometric dimension but not fixed number of counters. Recently, I proved that reachability in VASS of geometric dimension 2 is PSPACE-complete. In this talk, I will introduce the basic idea and interesting techniques for this specific case of geometric dimension 2.

---