Language Inclusion for Ambiguous Vector Addition Systems is Decidable

9^th August 2022, 13:00 Ashton Lecture Theatre
Dr. Piotr Hofman
Institute of Informatics, University of Warsaw

Abstract

We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASSes) with the acceptance condition defined by the set of accepting states. In general the problem of language equivalence is undecidable even for one-dimensional VASS-es, thus to get decidability restricted subclasses are investigated. The simplest example is a class of deterministic systems, for which language inclusion is decidable. In the talk we will look at the problem of language inclusion of an ambiguous VASS and show that it is decidable.

Based on a paper accepted to Concur 2022: Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
Joint work with Wojciech Czerwiński

Additional Materials

• https://arxiv.org/abs/2202.08033v1