Results 11 to 20 of about 160,476 (167)
Lambek calculus is NP-complete
Theoretical Computer Science, 2006 The main goal of the paper is to show that the derivability problems for the Lambek calculus (L) and for the Lambek calculus allowing empty premises (L*) are NP-complete. The construction of a reduction from the problem CSAT to the L-derivability and L*-derivability problems is described, and the correctness of this reduction is proved.
Pentus, Mati
openaire +3 more sources
On Involutive Nonassociative Lambek Calculus [PDF]
Journal of Logic, Language and Information, 2019 Involutive Nonassociative Lambek Calculus (InNL) is a nonassociative version of Noncommutative Multiplicative Linear Logic (MLL) (Abrusci in J Symb Log 56:1403–1451, 1991), but the multiplicative constants are not admitted. InNL adds two linear negations
W. Buszkowski
semanticscholar +2 more sources
Dialectica Categories for the Lambek Calculus [PDF]
Symposium on Logical Foundations of Computer Science, 2018 We revisit the old work of de Paiva on the models of the Lambek Calculus in dialectica models making sure that the syntactic details that were sketchy on the first version got completed and verified.
Valeria C V de Paiva, Harley D. Eades
semanticscholar +4 more sources
A Polynomial-Time Algorithm for the Lambek Calculus with Brackets of Bounded Order [PDF]
International Conference on Formal Structures for Computation and Deduction, 2017 Lambek calculus is a logical foundation of categorial grammar, a linguistic paradigm of grammar as logic and parsing as deduction. Pentus (2010) gave a polynomial-time algorithm for determ- ining provability of bounded depth formulas in the Lambek ...
M. Kanovich +3 more
semanticscholar +3 more sources
Classical Non-Associative Lambek Calculus
Studia Logica, 2002 We introduce non-associative linear logic, which may be seen as the classical version of the non-associative Lambek calculus. We define its sequent calculus, its theory of proof nets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.
de Groote, Philippe, Lamarche, François
openaire +3 more sources
Lambek Calculus with Banged Atoms for Parasitic Gaps
Workshop on Logic, Language, Information and Computation. Lambek Calculus is a non-commutative substructural logic for formalising linguistic constructions. However, its domain of applicability is limited to constructions with local dependencies.
M. Sadrzadeh, Lutz Straßburger
semanticscholar +2 more sources
The Lambek Calculus with Iteration: Two Variants [PDF]
Workshop on Logic, Language, Information and Computation, 2017 Formulae of the Lambek calculus are constructed using three binary connectives, multiplication and two divisions. We extend it using a unary connective, positive Kleene iteration.
S. Kuznetsov
semanticscholar +4 more sources
Proof nets for multiplicative cyclic linear logic and Lambek calculus [PDF]
Mathematical Structures in Computer Science, 2019 This paper presents a simple and intuitive syntax for proof nets of the multiplicative cyclic fragment (McyLL) of linear logic (LL). The main technical achievement of this work is to propose a correctness criterion that allows for sequentialization ...
V. Abrusci, Roberto Maieli
semanticscholar +2 more sources
Lambek vs. Lambek: Functorial vector space semantics and string diagrams for Lambek calculus
Annals of Pure and Applied Logic, 2013 29 pages, pending publication in Annals of Pure and Applied ...
Bob Coecke +2 more
openaire +5 more sources
Serial verb constructions and covert coordinations in Edo – an analysis in Type Logical Grammar
Journal of Language Modelling, 2021 Based on both syntactic and semantic criteria, Stewart (2001) and, following him, Baker and Stewart (1999), distinguish two types of serial verb constructions (SVC) and one type of covert coordination (CC) in Edo.
Ralf Naumann, Thomas Gamerschlag
doaj +1 more source