Consistent identification in the limit of any of the classes k-valued is NP-hard

DOI10.1007/3-540-48199-0_8MaRDI QIDQ4547846zbMATH OpenFDO

Authors Christophe Costa Florêncio

Publication date 21 August 2002

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2099/20990125

zbMATH Keywords

categorial grammarsformal language theorygrammatical inferencelearning theory

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of consistent identification of some classes of structure languages
• Consistent identification in the limit of rigid grammars from strings is NP-hard
• Three \(\sum^ P_ 2\)-complete problems in computational learning theory
• Finding consistent categorial grammars of bounded value: a parameterized approach
• On families of categorial grammars of bounded value, their learnability and related complexity questions

Cited in

(4)

• Learning tree languages from text
• Learning discrete categorial grammars from structures
• Consistent identification in the limit of rigid grammars from strings is NP-hard
• On families of categorial grammars of bounded value, their learnability and related complexity questions

This page was built for publication: Consistent identification in the limit of any of the classes \(k\)-valued is NP-hard

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