Switch to: References

Add citations

You must login to add citations.
  1. Complexity of the Infinitary Lambek Calculus with Kleene Star.Stepan Kuznetsov - 2021 - Review of Symbolic Logic 14 (4):946-972.
    We consider the Lambek calculus, or noncommutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an$\omega $-rule, and prove that the derivability problem in this calculus is$\Pi _1^0$-hard. This solves a problem left open by Buszkowski (2007), who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek grammar with (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • The Multiplicative-Additive Lambek Calculus with Subexponential and Bracket Modalities.Max Kanovich, Stepan Kuznetsov & Andre Scedrov - 2020 - Journal of Logic, Language and Information 30 (1):31-88.
    We give a proof-theoretic and algorithmic complexity analysis for systems introduced by Morrill to serve as the core of the CatLog categorial grammar parser. We consider two recent versions of Morrill’s calculi, and focus on their fragments including multiplicative connectives, additive conjunction and disjunction, brackets and bracket modalities, and the! subexponential modality. For both systems, we resolve issues connected with the cut rule and provide necessary modifications, after which we prove admissibility of cut. We also prove algorithmic undecidability for both (...)
    Download  
     
    Export citation  
     
    Bookmark