Geometrically 2-Dimensional Vector Addition System with States

Speaker(s)

Yangluo Zheng

Affiliation

Shanghai Jiao Tong University

Language of the talk

English

Date

Oct. 29, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Geometrically 2-Dimensional Vector Addition System with States

Seminar

Seminar Automata Theory

---

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.

---