On the complexity of consistent identification of some classes of structure languages

DOI10.1007/978-3-540-45257-7_8MaRDI QIDQ2754004zbMATH OpenFDO

Authors Christophe Costa Florêncio

Publication date 17 December 2001

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

Full work available at URL https://doi.org/10.1007/978-3-540-45257-7_8

zbMATH Keywords

classical categorial grammarcomplexity of learningconsistent learningidentification in the limitinductive inference

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 428239
• scientific article; zbMATH DE number 475424
• Consistent identification in the limit of rigid grammars from strings is NP-hard
• Algorithmic Learning Theory
• Identification in the Limit of k,l-Substitutable Context-Free Languages
• On the complexity of a mildly context-sensitive language class
• scientific article; zbMATH DE number 996379
• Complexity of certain decision problems about congruential languages
• On the structure of recognizable languages of dependence graphs
• scientific article; zbMATH DE number 5519566

Cited in

(4)

• Identification in the Limit of k,l-Substitutable Context-Free Languages
• Consistent identification in the limit of rigid grammars from strings is NP-hard
• Consistent identification in the limit of any of the classes k-valued is NP-hard
• Constants and label-equivalence: a decision procedure for reflexive regular splicing languages

This page was built for publication: On the complexity of consistent identification of some classes of structure languages

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