Separability and Non-Determinizability of WSTS
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929367281565696 |
|---|---|
| author | Czerwiński, Wojciech Keskin, Eren Lasota, Sławomir Meyer, Roland Muskalla, Sebastian Kumar, K Narayan Saivasan, Prakash |
| author_facet | Czerwiński, Wojciech Keskin, Eren Lasota, Sławomir Meyer, Roland Muskalla, Sebastian Kumar, K Narayan Saivasan, Prakash |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02736 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Separability and Non-Determinizability of WSTS Czerwiński, Wojciech Keskin, Eren Lasota, Sławomir Meyer, Roland Muskalla, Sebastian Kumar, K Narayan Saivasan, Prakash 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. |
| title | Separability and Non-Determinizability of WSTS |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2305.02736 |