Equivalence of finite non-deterministic logical matrices is undecidable
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909433221611520 |
|---|---|
| author | Caleiro, Carlos Filipe, Pedro Marcelino, Sérgio |
| author_facet | Caleiro, Carlos Filipe, Pedro Marcelino, Sérgio |
| contents | The notion of a non-deterministic logical matrix (where connectives are interpreted as multi-functions) extends the traditional semantics for propositional logics based on logical matrices (where connectives are interpreted as functions). This extension allows for finitely characterizing a much wider class of logics, and has proven decisive in a myriad of recent compositionality results. In this paper we show that the added expressivity brought by non-determinism also has its drawbacks, and in particular that the problem of determining whether two given finite non-deterministic matrices are equivalent, in the sense that they induce the same logic, becomes undecidable. We also discuss some workable sufficient conditions and particular cases, namely regarding rexpansion homomorphisms and bridges to calculi. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_14057 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Equivalence of finite non-deterministic logical matrices is undecidable Caleiro, Carlos Filipe, Pedro Marcelino, Sérgio Logic Logic in Computer Science 03B22, 03B35, 03B50, 03B60, The notion of a non-deterministic logical matrix (where connectives are interpreted as multi-functions) extends the traditional semantics for propositional logics based on logical matrices (where connectives are interpreted as functions). This extension allows for finitely characterizing a much wider class of logics, and has proven decisive in a myriad of recent compositionality results. In this paper we show that the added expressivity brought by non-determinism also has its drawbacks, and in particular that the problem of determining whether two given finite non-deterministic matrices are equivalent, in the sense that they induce the same logic, becomes undecidable. We also discuss some workable sufficient conditions and particular cases, namely regarding rexpansion homomorphisms and bridges to calculi. |
| title | Equivalence of finite non-deterministic logical matrices is undecidable |
| topic | Logic Logic in Computer Science 03B22, 03B35, 03B50, 03B60, |
| url | https://arxiv.org/abs/2412.14057 |