Complexity of Lambek calculi with modalities and of total derivability in grammars

DOI10.1007/s10469-021-09657-5OpenAlexW4200395486MaRDI QIDQ2066100

Stepan Kuznetsov, E. M. Fofanova, B. N. Karlov, Sergey M. Dudakov

Publication date: 13 January 2022

Published in: Algebra and Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10469-021-09657-5

zbMATH Keywords

algorithmic complexitycontext-free grammarsLambek calculussubstructural logicexponentialrelevant modalitytotal derivability

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX) Group theory and generalizations (20-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Linear logic
• Decision problems for propositional linear logic
• Lambek calculus is NP-complete
• Recognition of derivability for the Lambek calculus with one division
• Undecidability of the Lambek Calculus with a Relevant Modality
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Subexponentials in non-commutative linear logic

This page was built for publication: Complexity of Lambek calculi with modalities and of total derivability in grammars