arXiv Open Access 2025

Language Equivalence is Undecidable in VASS with Restricted Nondeterminism

Wojciech Czerwiński Łukasz Orlikowski

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.FL cs.LO

Penulis (2)

Wojciech Czerwiński

Łukasz Orlikowski

Format Sitasi

APA MLA BibTeX

Czerwiński, W., Orlikowski, Ł. (2025). Language Equivalence is Undecidable in VASS with Restricted Nondeterminism. https://arxiv.org/abs/2510.21514

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓