Vector addition systems and regular languages

摘要

Necessary and sufficient conditions are established for Vector Addition Systems to define regular languages. An algorithm is designed to decide whether these conditions are satisfied. The reachability problem for such Vector Addition Systems is shown to be decidable.