English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Regular Separability in Büchi VASS

MPS-Authors
/persons/resource/persons274580

Baumann,  Pascal
Group G. Zetzsche, Max Planck Institute for Software Systems, Max Planck Society;

/persons/resource/persons230970

Zetzsche,  Georg
Group G. Zetzsche, Max Planck Institute for Software Systems, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2301.11242.pdf
(Preprint), 941KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Baumann, P., Meyer, R., & Zetzsche, G. (2023). Regular Separability in Büchi VASS. Retrieved from https://arxiv.org/abs/2301.11242.


Cite as: https://hdl.handle.net/21.11116/0000-000C-B71D-6
Abstract
We study the ($\omega$-)regular separability problem for B\"uchi VASS
languages: Given two B\"uchi VASS with languages $L_1$ and $L_2$, check whether
there is a regular language that fully contains $L_1$ while remaining disjoint
from $L_2$. We show that the problem is decidable in general and
PSPACE-complete in the 1-dimensional case, assuming succinct counter updates.
The results rely on several arguments. We characterize the set of all regular
languages disjoint from $L_2$. Based on this, we derive a (sound and complete)
notion of inseparability witnesses, non-regular subsets of $L_1$. Finally, we
show how to symbolically represent inseparability witnesses and how to check
their existence.