Relevant S is Undecidable
| Authors | |
|---|---|
| Publication date | 2024 |
| Book title | Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science |
| ISBN (electronic) |
|
| Event | 39th Annual ACM/IEEE Symposium on Logic in Computer Science |
| Article number | 51 |
| Number of pages | 8 |
| Publisher | New York, New York: The Association for Computing Machinery |
| Organisations |
|
| Abstract |
Since the introduction of the semilattice relevant logic S by [Urquhart 1972, 1973], its decision problem has persisted as an open problem. [Urquhart 1984] showed that many relevant logics are undecidable, yet S eluded these techniques. Eventually, this led experts, including [Urquhart 2016], to conjecture that S is decidable. Contrary to this conjecture, by interpreting a tiling problem, we show that S is undecidable. |
| Document type | Conference contribution |
| Language | English |
| Published at | https://doi.org/10.1145/3661814.3662128 |
| Downloads |
3661814.3662128
(Final published version)
|
| Permalink to this page | |
