Complexity of Nonassociative Lambek Calculus with classical logic
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917882231783424 |
|---|---|
| author | Płaczek, Paweł |
| author_facet | Płaczek, Paweł |
| contents | The Nonassociative Lambek Calculus (NL) represents a logic devoid of the structural rules of exchange, weakening, and contraction, and it does not presume the associativity of its connectives. Its finitary consequence relation is decidable in polynomial time. However, the addition of classical connectives conjunction and disjunction (FNL) makes the consequence relation undecidable. Interestingly, if these connectives are distributive, the consequence relation is decidable in exponential time. This paper provides the proof that we can merge classical logic and NL (i.e. BFNL), and still the consequence relation is decidable in exponential time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00493 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity of Nonassociative Lambek Calculus with classical logic Płaczek, Paweł Logic in Computer Science Computational Complexity F.4.1 The Nonassociative Lambek Calculus (NL) represents a logic devoid of the structural rules of exchange, weakening, and contraction, and it does not presume the associativity of its connectives. Its finitary consequence relation is decidable in polynomial time. However, the addition of classical connectives conjunction and disjunction (FNL) makes the consequence relation undecidable. Interestingly, if these connectives are distributive, the consequence relation is decidable in exponential time. This paper provides the proof that we can merge classical logic and NL (i.e. BFNL), and still the consequence relation is decidable in exponential time. |
| title | Complexity of Nonassociative Lambek Calculus with classical logic |
| topic | Logic in Computer Science Computational Complexity F.4.1 |
| url | https://arxiv.org/abs/2501.00493 |