تقرير
Separability and Non-Determinizability of WSTS
| العنوان: | Separability and Non-Determinizability of WSTS |
|---|---|
| المؤلفون: | Czerwiński, Wojciech, Keskin, Eren, Lasota, Sławomir, Meyer, Roland, Muskalla, Sebastian, Kumar, K Narayan, Saivasan, Prakash |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Formal Languages and Automata Theory |
| الوصف: | We study the languages recognized by well-structured transition systems (WSTS) with upward and downward compatibility. Our first result shows that every pair of disjoint WSTS languages is regularly separable: there is a regular language containing one of them while 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. Our second result shows that the languages recognized by deterministic WSTS form a strict subclass of the languages recognized by all WSTS: we give a non-deterministic WSTS language that we prove cannot be recognized by a deterministic WSTS. The proof relies on a novel characterization of the languages accepted by deterministic WSTS. Comment: This paper is the journal version of the CONCUR23 paper "Separability and Non-Determinizability of WSTS'', which can be found in the previous version of this arxiv document. It covers both papers about regular separability in WSTS: the CONCUR23 paper and its predecessor the CONCUR18 paper. As this version does not contain an appendix, please refer to the previous version for missing proofs |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2305.02736 |
| رقم الأكسشن: | edsarx.2305.02736 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |