History Deterministic Vector Addition Systems

In this talk, we consider History-determinism, a restricted form of non-determinism, for Vector Addition Systems with States (VASS) when used as acceptors to recognise languages of finite words, both with coverability and reachability acceptance. History-determinism requires that the non-deterministic choices can be resolved on-the-fly; based on the past andwithout jeopardising acceptance of any possible continuation of the input word. Our results show that the history-deterministic (HD) VASS sit strictly between deterministic and non-deterministic VASS. We compare the relative expressiveness of HD systems, and closure-properties of the induced language classes, with coverability and reachability semantics, with or without $\epsilon$ labelled transitions. With two or more counters HD-VASS are essentially able to approximate 2-counter Minsky machines, leading to several undecidability results. It is undecidable whether an VASS is history-deterministic, or if a language equivalent history-deterministic VASS exists. Checking language inclusion between history-deterministic $2$-VASS is also undecidable. This talk is based on joint work with Patrick Totzke and David Purser. Contributed talk given by Sougata Bose

Authors

• Sougata Bose UMONS - Université de Mons

Keywords

No keywords are indexed for this paper.