Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.24
URN: urn:nbn:de:0030-drops-70091
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7009/
Clemente, Lorenzo ; Czerwinski, Wojciech ; Lasota, Slawomir ; Paperman, Charles
Separability of Reachability Sets of Vector Addition Systems
| pdf-format: |
|
Abstract
Given two families of sets F and G, the F-separability problem for G asks whether for two given sets U, V in G there exists a set S in F, such that U is included in S and V is disjoint with S. We consider two families of sets F: modular sets S which are subsets of N^d, defined as unions of equivalence classes modulo some natural number n in N, and unary sets, which extend modular sets by requiring equality below a threshold n, and equivalence modulo n above n. Our main result is decidability of modular- and unary-separability for the class G of reachability sets of Vector Addition Systems, Petri Nets, Vector Addition Systems with States, and for sections thereof.
BibTeX - Entry
@InProceedings{clemente_et_al:LIPIcs:2017:7009,
author = {Lorenzo Clemente and Wojciech Czerwinski and Slawomir Lasota and Charles Paperman},
title = {{Separability of Reachability Sets of Vector Addition Systems}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {24:1--24:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7009},
URN = {urn:nbn:de:0030-drops-70091},
doi = {10.4230/LIPIcs.STACS.2017.24},
annote = {Keywords: separability, Petri nets, modular sets, unary sets, decidability}
}
| Keywords: | separability, Petri nets, modular sets, unary sets, decidability | |
| Seminar: | 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 06.03.2017 |
