Learning Lambek grammars from proof frames

DOI10.1007/978-3-642-54789-8_7MaRDI QIDQ5414961zbMATH OpenOpenAlexFDO

Authors Roberto Bonato, Christian Retoré

Publication date 8 May 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0576

Mathematics Subject Classification ID

Computational learning theory (68Q32) Logic of natural languages (03B65) Grammars and rewriting systems (68Q42)

Abstract: In addition to their limpid interface with semantics, categorial grammars enjoy another important property: learnability. This was first noticed by Buskowsky and Penn and further studied by Kanazawa, for Bar-Hillel categorial grammars. What about Lambek categorial grammars? In a previous paper we showed that product free Lambek grammars where learnable from structured sentences, the structures being incomplete natural deductions. These grammars were shown to be unlearnable from strings by Foret and Le Nir. In the present paper we show that Lambek grammars, possibly with product, are learnable from proof frames that are incomplete proof nets. After a short reminder on grammatical inference `a la Gold, we provide an algorithm that learns Lambek grammars with product from proof frames and we prove its convergence. We do so for 1-valued also known as rigid Lambek grammars with product, since standard techniques can extend our result to $k$-valued grammars. Because of the correspondence between cut-free proof nets and normal natural deductions, our initial result on product free Lambek grammars can be recovered. We are sad to dedicate the present paper to Philippe Darondeau, with whom we started to study such questions in Rennes at the beginning of the millennium, and who passed away prematurely. We are glad to dedicate the present paper to Jim Lambek for his 90 birthday: he is the living proof that research is an eternal learning process.

Recommendations

• scientific article; zbMATH DE number 2019598
• scientific article; zbMATH DE number 1786551
• K-valued non-associative Lambek grammars are learnable from function-argument structures
• From proof trees in Lambek calculus to Ajdukiewicz Bar-Hillel elimination binary trees
• \(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures

Cites work

• scientific article; zbMATH DE number 1233727 (Why is no real title available?)
• scientific article; zbMATH DE number 2134917 (Why is no real title available?)
• scientific article; zbMATH DE number 3251420 (Why is no real title available?)
• scientific article; zbMATH DE number 3254899 (Why is no real title available?)
• A linear algorithm for MLL proof net correctness and sequentialization
• Categorial grammars determined from linguistic data by unification
• Derivational minimalism
• Finding patterns common to a set of strings
• How to Split Recursive Automata
• Inductive inference of formal languages from positive data
• Language identification in the limit
• Learnability of type-logical grammars
• The Mathematics of Sentence Structure
• The correspondence between cut-elimination and normalization
• The logic of categorial grammars. A deductive account of natural language syntax and semantics
• Using tree transducers for grammatical inference

Cited in

(6)

• scientific article; zbMATH DE number 1786551 (Why is no real title available?)
• From proof trees in Lambek calculus to Ajdukiewicz Bar-Hillel elimination binary trees
• \(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures
• K-valued non-associative Lambek grammars are learnable from function-argument structures
• Good types are useful for learning
• scientific article; zbMATH DE number 2019598 (Why is no real title available?)

This page was built for publication: Learning Lambek grammars from proof frames

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5414961)