License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2018.35
URN: urn:nbn:de:0030-drops-95733
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9573/
Go to the corresponding LIPIcs Volume Portal

Czerwinski, Wojciech ; Lasota, Slawomir ; Meyer, Roland ; Muskalla, Sebastian ; Narayan Kumar, K. ; Saivasan, Prakash

Regular Separability of Well-Structured Transition Systems

pdf-format:
LIPIcs-CONCUR-2018-35.pdf (0.5 MB)

Abstract

We investigate the languages recognized by well-structured transition systems (WSTS) with upward and downward compatibility. Our first result shows that, under very mild assumptions, every two disjoint WSTS languages are regular separable: There is a regular language containing one of them and being disjoint from the other. As a consequence, if a language as well as its complement are both recognized by WSTS, then they are necessarily regular. In particular, no subclass of WSTS languages beyond the regular languages is closed under complement. Our second result shows that for Petri nets, the complexity of the backwards coverability algorithm yields a bound on the size of the regular separator. We complement it by a lower bound construction.

BibTeX - Entry

@InProceedings{czerwinski_et_al:LIPIcs:2018:9573,
  author =	{Wojciech Czerwinski and Slawomir Lasota and Roland Meyer and Sebastian Muskalla and K. Narayan Kumar and Prakash Saivasan},
  title =	{{Regular Separability of Well-Structured Transition Systems}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9573},
  URN =		{urn:nbn:de:0030-drops-95733},
  doi =		{10.4230/LIPIcs.CONCUR.2018.35},
  annote =	{Keywords: regular separability, wsts, coverability languages, Petri nets}
}

Keywords: regular separability, wsts, coverability languages, Petri nets
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI