On families of categorial grammars of bounded value, their learnability and related complexity questions

DOI10.1016/J.TCS.2012.05.016zbMATH1252.68169OpenAlexW2058320114MaRDI QIDQ714784FDOQ714784

Authors Christophe Costa Florêncio, Henning Fernau

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.05.016

zbMATH Keywords

parameterized complexityregular tree languagesfinite elasticityidentification in the limitgrammar inductioncategorial grammarHölder norms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Recommendations

• Finding consistent categorial grammars of bounded value: a parameterized approach
• scientific article; zbMATH DE number 1233727
• scientific article; zbMATH DE number 1786549
• On learnability of restricted classes of categorial grammars
• Identification in the limit of categorial grammars

Cites work

• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 5605062 (Why is no real title available?)
• scientific article; zbMATH DE number 3716830 (Why is no real title available?)
• scientific article; zbMATH DE number 67629 (Why is no real title available?)
• scientific article; zbMATH DE number 1233727 (Why is no real title available?)
• scientific article; zbMATH DE number 1351108 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 592370 (Why is no real title available?)
• scientific article; zbMATH DE number 976409 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2019594 (Why is no real title available?)
• scientific article; zbMATH DE number 2019616 (Why is no real title available?)
• scientific article; zbMATH DE number 745858 (Why is no real title available?)
• scientific article; zbMATH DE number 1390085 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Categorial grammars determined from linguistic data by unification
• Comparison of some descriptional complexities of 0L systems obtained by a unifying approach
• Descriptional complexity -- an introductory survey
• Finding consistent categorial grammars of bounded value: a parameterized approach
• Hölder Norms and a Hierarchy Theorem for Parameterized Classes of CCG
• Ignoring data may be the only way to learn efficiently
• Improved upper bounds for vertex cover
• Inductive inference of formal languages from positive data
• Inference of Reversible Languages
• Language identification in the limit
• On miniaturized problems in parameterized complexity theory
• Reflections on multivariate algorithmics and problem parameterization
• The Mathematics of Sentence Structure
• The NP-completeness column
• The graph isomorphism disease
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology
• \(K\)-valued non-associative Lambek grammars are learnable from function-argument structures

Cited in

(7)

• scientific article; zbMATH DE number 1233727 (Why is no real title available?)
• \(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures
• Finding consistent categorial grammars of bounded value: a parameterized approach
• scientific article; zbMATH DE number 1786549 (Why is no real title available?)
• Learning Tree Languages
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• A multi-parameter analysis of hard problems on deterministic finite automata

This page was built for publication: On families of categorial grammars of bounded value, their learnability and related complexity questions

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