Language Equivalence is Undecidable in VASS with Restricted Nondeterminism
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917040016588800 |
|---|---|
| author | Czerwiński, Wojciech Orlikowski, Łukasz |
| author_facet | Czerwiński, Wojciech Orlikowski, Łukasz |
| contents | In this work, we extend undecidability of language equivalence for two-dimensional Vector Addition System with States (VASS) accepting by coverability condition. We show that the problem is undecidable even when one of the two-dimensional VASSs is deterministic and the other is history-deterministic. Moreover, we observe, that the languages of two history-deterministic VASSs are equal if and only if each can simulate the other. This observation allows us to extend the undecidability to any equivalence relation between two-sided simulation and language equivalence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21514 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Language Equivalence is Undecidable in VASS with Restricted Nondeterminism Czerwiński, Wojciech Orlikowski, Łukasz Formal Languages and Automata Theory Logic in Computer Science In this work, we extend undecidability of language equivalence for two-dimensional Vector Addition System with States (VASS) accepting by coverability condition. We show that the problem is undecidable even when one of the two-dimensional VASSs is deterministic and the other is history-deterministic. Moreover, we observe, that the languages of two history-deterministic VASSs are equal if and only if each can simulate the other. This observation allows us to extend the undecidability to any equivalence relation between two-sided simulation and language equivalence. |
| title | Language Equivalence is Undecidable in VASS with Restricted Nondeterminism |
| topic | Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2510.21514 |