Complexity of Nonassociative Lambek Calculus with Classical and Intuitionistic Logic

Key Points

• The research aims to explore the complexities of the Nonassociative Lambek Calculus when integrated with classical and intuitionistic logic, focusing on the decidability of consequence relations.
• Examined the Nonassociative Lambek Calculus devoid of structural rules.
• Added classical connectives conjunction and disjunction to analyze impact on decidability.
• Analyzed the impact of distributiveness on consequence relations.
• Merged classical logic and intuitionistic logic with NL for complexity evaluation.
• Consequence relations in Nonassociative Lambek Calculus are decidable in polynomial time.
• Adding classical connectives makes some consequence relations undecidable.
• Distributive classical connectives lead to exponential time decidability.
• Integrating classical and intuitionistic logic still results in decidable consequences in exponential time.