Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Proof-theoretic aspects of NLλ

Abstract : We present a proof-theoretic analysis of the logic NLλ (Barker & Shan 2014, Barker 2019). We notably introduce a novel calculus of proof nets and prove it is sound and complete with respect to the sequent calculus for the logic. We study decidability and complexity of the logic using this new calculus, proving a new upper bound for complexity of the logic (showing it is in NP) and a new lower bound for the class of formal language generated by the formalism (mildly context-sensitive languages extended with a permutation closure operation). Finally, thanks to this new calculus, we present a novel comparison between NLλ and the hybrid type-logical grammars of Kubota & Levine (2020). We show there is an unexpected convergence of the natural language analyses proposed in the two formalism. In addition to studying the proof-theoretic properties of NLλ, we greatly extends its linguistic coverage.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02973980
Contributor : Richard Moot <>
Submitted on : Wednesday, October 21, 2020 - 2:32:47 PM
Last modification on : Friday, June 4, 2021 - 12:32:02 PM
Long-term archiving on: : Friday, January 22, 2021 - 6:46:16 PM

Files

nllam.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : lirmm-02973980, version 1
  • ARXIV : 2010.12223

Collections

Citation

Richard Moot. Proof-theoretic aspects of NLλ. 2020. ⟨lirmm-02973980⟩

Share

Metrics

Record views

43

Files downloads

24