Separability of Reachability Sets of Vector Addition Systems

DOI10.4230/LIPICS.STACS.2017.24zbMATH Open1402.68132arXiv1609.00214OpenAlexW2962811419MaRDI QIDQ4636622FDOQ4636622

Wojciech Czerwiński, Charles Paperman, Lorenzo Clemente, Sławomir Lasota

Publication date: 19 April 2018

Abstract: Given two families of sets $mathcalF$ and $mathcalG$, the $mathcalF$ separability problem for $mathcalG$ asks whether for two given sets $U,VinmathcalG$ there exists a set $SinmathcalF$, such that $U$ is included in $S$ and $V$ is disjoint with $S$. We consider two families of sets $mathcalF$: modular sets $Ssubseteqmathbb{N}^d$, defined as unions of equivalence classes modulo some natural number $ninmathbbN$, and unary sets. Our main result is decidability of modular and unary separability for the class $mathcalG$ of reachability sets of Vector Addition Systems, Petri Nets, Vector Addition Systems with States, and for sections thereof.

Full work available at URL: https://arxiv.org/abs/1609.00214

zbMATH Keywords

separabilitydecidabilityPetri netsmodular setsunary sets

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Unboundedness Problems for Languages of Vector Addition Systems.
• Demystifying Reachability in Vector Addition Systems

This page was built for publication: Separability of Reachability Sets of Vector Addition Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636622)