Bose, S, Purser, D 
ORCID: 0000-0003-0394-1634 and Totzke, P ORCID: 0000-0001-5274-8190
(2023)
History-Deterministic Vector Addition Systems.
In: 34th International Conference on Concurrency Theory (CONCUR 2023)., 2023-9-19 - 2023-9-22, University of Antwerp, Belgium.
|
PDF
concur.pdf - Author Accepted Manuscript Download (816kB) | Preview |
Abstract
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. History-determinism requires that the non-deterministic choices can be resolved on-the-fly; based on the past and without 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 regardless of the number of counters. We compare the relative expressiveness of HD systems, and closure-properties of the induced language classes, with coverability and reachability semantics, and with and without ε-labelled transitions. Whereas in dimension 1, inclusion and regularity remain decidable, from dimension two onwards, HD-VASS with suitable resolver strategies, are essentially able to simulate 2-counter Minsky machines, leading to several undecidability results: It is undecidable whether a VASS is history-deterministic, or if a language equivalent history-deterministic VASS exists. Checking language inclusion between history-deterministic 2-VASS is also undecidable.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 10 Jul 2023 13:05 |
| Last Modified: | 11 Oct 2023 15:31 |
| DOI: | 10.4230/LIPIcs.CONCUR.2023.18 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171612 |
Dimensions
Dimensions
