Article contents
UNDECIDABILITY OF CONSEQUENCE RELATION IN FULL NON-ASSOCIATIVE LAMBEK CALCULUS
Published online by Cambridge University Press: 22 April 2015
Abstract
We prove that the consequence relation in the Full Non-associative Lambek Calculus is undecidable. An encoding of the halting problem for 2-tag systems using finitely many sequents in the language {⋅,∨} is presented. Therefore already the consequence relation in this fragment is undecidable. Moreover, the construction works even when the structural rules of exchange and contraction are added.
Keywords
- Type
- Articles
- Information
- Copyright
- Copyright © The Association for Symbolic Logic 2015
References
REFERENCES
- 4
- Cited by