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

DOI10.1016/j.tcs.2012.05.016zbMath1252.68169OpenAlexW2058320114MaRDI QIDQ714784

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

finite elasticityregular tree languagesHölder normsparameterized complexityidentification in the limitgrammar inductioncategorial grammar

Mathematics Subject Classification ID

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

Related Items (3)

Learning Tree Languages ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Cites Work

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

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