The structure of intrinsic complexity of learning

DOI10.2307/2275636zbMath0895.68121OpenAlexW2122008636MaRDI QIDQ4382469

Arun Sharma, Sanjay Jain

Publication date: 2 September 1998

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275636

zbMATH Keywords

reducibilityintrinsic complexity of learninglanguage learning machine

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (10)

Intrinsic complexity of learning geometrical concepts from positive data ⋮ How rich is the structure of the intrinsic complexity of learning ⋮ An approach to intrinsic complexity of uniform learning ⋮ Mind change speed-up for learning languages from positive data ⋮ Intrinsic complexity of partial learning ⋮ On the intrinsic complexity of learning recursive functions ⋮ Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data ⋮ Ordinal mind change complexity of language identification ⋮ Induction by enumeration ⋮ Language learning from texts: Degrees of intrinsic complexity and their characterizations

Cites Work

• Unnamed Item
• Finding patterns common to a set of strings
• The intrinsic complexity of language identification
• Inductive inference of formal languages from positive data
• Periodicity in generations of automata
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Language identification in the limit

This page was built for publication: The structure of intrinsic complexity of learning