The Logic for a Mildly Context-Sensitive Fragment of the Lambek-Grishin Calculus

• URL: http://arxiv.org/abs/2101.03634v1
• Date: Sun, 10 Jan 2021 22:28:05 GMT
• Title: The Logic for a Mildly Context-Sensitive Fragment of the Lambek-Grishin Calculus
• Authors: Hiroyoshi Komatsu
• Abstract summary: We present a proof-theoretic characterization of tree-adjoining languages based on the Lambek-Grishin calculus. Several new techniques are introduced for the proofs, such as purely structural connectives, usefulness, and a graph-theoretic argument on proof nets for HLG.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While context-free grammars are characterized by a simple proof-theoretic grammatical formalism namely categorial grammar and its logic the Lambek calculus, no such characterizations were known for tree-adjoining grammars, and even for any mildly context-sensitive languages classes in the last forty years despite some efforts. We settle this problem in this paper. On the basis of the existing fragment of the Lambek-Grishin calculus which captures tree-adjoining languages, we present a logic called HLG: a proof-theoretic characterization of tree-adjoining languages based on the Lambek-Grishin calculus restricted to Hyperedge-replacement grammar with rank two studied by Moot. HLG is defined in display calculus with cut-admissibility. Several new techniques are introduced for the proofs, such as purely structural connectives, usefulness, and a graph-theoretic argument on proof nets for HLG.

Related papers

• Conjunctive categorial grammars and Lambek grammars with additives [49.1574468325115]
  A new family of categorial grammars is proposed, defined by enriching basic categorial grammars with a conjunction operation. It is also shown that categorial grammars with conjunction can be naturally embedded into the Lambek calculus with conjunction and disjunction operations.
  arXiv  Detail & Related papers  (2024-05-26T18:53:56Z)
• $O_2$ is a multiple context-free grammar: an implementation-, formalisation-friendly proof [0.0]
  Classifying languages according to the expressiveness of grammars able to generate them is a fundamental problem in computational linguistics. This paper analyses the existing proofs from the computational and the proof-theoretical point of views systematically studying whether each proof can lead to a verified (i.e., checked by a proof assistant) algorithm parsing balanced languages via MCFGs.
  arXiv  Detail & Related papers  (2024-05-15T14:51:11Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  We propose MURMUR, a neuro-symbolic modular approach to text generation from semi-structured data with multi-step reasoning. We conduct experiments on two data-to-text generation tasks like WebNLG and LogicNLG.
  arXiv  Detail & Related papers  (2022-12-16T17:36:23Z)
• Structural generalization is hard for sequence-to-sequence models [85.0087839979613]
  Sequence-to-sequence (seq2seq) models have been successful across many NLP tasks. Recent work on compositional generalization has shown that seq2seq models achieve very low accuracy in generalizing to linguistic structures that were not seen in training.
  arXiv  Detail & Related papers  (2022-10-24T09:03:03Z)
• VLGrammar: Grounded Grammar Induction of Vision and Language [86.88273769411428]
  We study grounded grammar induction of vision and language in a joint learning framework. We present VLGrammar, a method that uses compound probabilistic context-free grammars (compound PCFGs) to induce the language grammar and the image grammar simultaneously.
  arXiv  Detail & Related papers  (2021-03-24T04:05:08Z)
• Proof-theoretic aspects of NL$\lambda$ [0.0]
  We present a proof-theoretic analysis of the logic NL$lambda$. We introduce a novel calculus of proof nets and prove it is sound and complete with respect to the sequent calculus for the logic. We show there is an unexpected convergence of the natural language analyses proposed in the two formalisms.
  arXiv  Detail & Related papers  (2020-10-23T08:13:39Z)
• Neural Proof Nets [0.8379286663107844]
  We propose a neural variant of proof nets based on Sinkhorn networks, which allows us to translate parsing as the problem of extracting primitive primitive permuting them into alignment. We test our approach on AEThel, where it manages to correctly transcribe raw text sentences into proofs and terms of the linear lambda-calculus with an accuracy of as high as 70%.
  arXiv  Detail & Related papers  (2020-09-26T22:48:47Z)
• Logical foundations for hybrid type-logical grammars [0.0]
  This paper explores proof-theoretic aspects of hybrid type-logical grammars. We prove some basic properties of the calculus, such as normalisation and the subformula property. We present both a sequent and a proof net calculus for hybrid type-logical grammars.
  arXiv  Detail & Related papers  (2020-09-22T08:26:14Z)
• The Return of Lexical Dependencies: Neural Lexicalized PCFGs [103.41187595153652]
  We present novel neural models of lexicalized PCFGs which allow us to overcome sparsity problems. Experiments demonstrate that this unified framework results in stronger results on both representations than achieved when either formalism alone.
  arXiv  Detail & Related papers  (2020-07-29T22:12:49Z)
• Logical Natural Language Generation from Open-Domain Tables [107.04385677577862]
  We propose a new task where a model is tasked with generating natural language statements that can be emphlogically entailed by the facts. To facilitate the study of the proposed logical NLG problem, we use the existing TabFact dataset citechen 2019tabfact featured with a wide range of logical/symbolic inferences. The new task poses challenges to the existing monotonic generation frameworks due to the mismatch between sequence order and logical order.
  arXiv  Detail & Related papers  (2020-04-22T06:03:10Z)
• Traduction des Grammaires Cat\'egorielles de Lambek dans les Grammaires Cat\'egorielles Abstraites [0.0]
  This internship report is to demonstrate that every Lambek Grammar can be, not entirely but efficiently, expressed in Abstract Categorial Grammars (ACG) The main idea is to transform the type rewriting system of LGs into that of Context-Free Grammars (CFG) by erasing introduction and elimination rules and generating enough axioms so that the cut rule suffices. Although the underlying algorithm was not fully implemented, this proof provides another argument in favour of the relevance of ACGs in Natural Language Processing.
  arXiv  Detail & Related papers  (2020-01-23T18:23:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.