Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.20415 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915265662418944 |
|---|---|
| author | Nakamura, Yoshiki |
| author_facet | Nakamura, Yoshiki |
| contents | We show that the emptiness (unsatisfiability) problem is undecidable and $\mathrmΠ^{0}_{1}$-complete for deterministic propositional while programs with (graph) loop. To this end, we introduce a hypothesis elimination using loops. Using this, we give reductions from the complement of the periodic domino problem.
Moreover, as a corollary via hypothesis eliminations, we also show that the equational theory is $\mathrmΠ^{0}_{1}$-complete for the positive calculus of relations with transitive closure and difference. Additionally, we show that the emptiness problem is PSPACE-complete for the existential calculus of relations with transitive closure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20415 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Undecidability of the Emptiness Problem of Deterministic Propositional While Programs with Graph Loop: Hypothesis Elimination Using Loops Nakamura, Yoshiki Logic in Computer Science We show that the emptiness (unsatisfiability) problem is undecidable and $\mathrmΠ^{0}_{1}$-complete for deterministic propositional while programs with (graph) loop. To this end, we introduce a hypothesis elimination using loops. Using this, we give reductions from the complement of the periodic domino problem. Moreover, as a corollary via hypothesis eliminations, we also show that the equational theory is $\mathrmΠ^{0}_{1}$-complete for the positive calculus of relations with transitive closure and difference. Additionally, we show that the emptiness problem is PSPACE-complete for the existential calculus of relations with transitive closure. |
| title | Undecidability of the Emptiness Problem of Deterministic Propositional While Programs with Graph Loop: Hypothesis Elimination Using Loops |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2504.20415 |