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

DOI10.1016/J.TCS.2012.05.016zbMATH Open1252.68169OpenAlexW2058320114MaRDI QIDQ714784FDOQ714784

Henning Fernau, Christophe Costa Florêncio

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 limit[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=H%EF%BF%BD%EF%BF%BDlder+norms&go=Go H��lder norms]grammar inductioncategorial grammar

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)

Cites Work

• Inductive inference of formal languages from positive data
• Language identification in the limit
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved upper bounds for vertex cover
• The graph isomorphism disease
• Title not available (Why is that?)
• Inference of Reversible Languages
• The Mathematics of Sentence Structure
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ignoring data may be the only way to learn efficiently
• Title not available (Why is that?)
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Title not available (Why is that?)
• Title not available (Why is that?)
• On miniaturized problems in parameterized complexity theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Categorial grammars determined from linguistic data by unification
• Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach
• Hölder Norms and a Hierarchy Theorem for Parameterized Classes of CCG
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• k-Valued Non-Associative Lambek Grammars are Learnable from Function-Argument Structures
• Title not available (Why is that?)
• The NP-completeness column
• Comparison of some descriptional complexities of 0L systems obtained by a unifying approach

Cited In (6)

• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• \(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures
• Title not available (Why is that?)
• Learning Tree Languages
• A multi-parameter analysis of hard problems on deterministic finite automata
• Title not available (Why is that?)

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)