Ordinal mind change complexity of language identification

DOI10.1016/S0304-3975(99)00005-5zbMath0954.68082OpenAlexW2103385338MaRDI QIDQ1575840

Andris Ambainis, Sanjay Jain, Arun Sharma

Publication date: 23 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00005-5

zbMATH Keywords

inductive inferencelearning machine

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (14)

Generalized notions of mind change complexity ⋮ Counting extensional differences in BC-learning ⋮ Parsimony hierarchies for inductive inference ⋮ On ordinal VC-dimension and some notions of complexity ⋮ On the classification of recursive languages ⋮ On the intrinsic complexity of learning recursive functions ⋮ Learning with ordinal-bounded memory from positive data ⋮ Set systems: order types, continuous nondeterministic deformations, and quasi-orders ⋮ Nonmonotonicity in the framework of parametric logic ⋮ Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data ⋮ Mind change efficient learning ⋮ Learning algebraic structures from text ⋮ On learning unions of pattern languages and tree patterns in the mistake bound model. ⋮ Unifying logic, topology and learning in parametric logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of identification criteria for machine inductive inference
• Monotonic and dual monotonic language learning
• Elementary formal systems, intrinsic complexity, and procrastination
• Monotonic and non-monotonic inductive inference
• Finding patterns common to a set of strings
• Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
• On the role of procrastination in machine learning
• Rich classes inferable from positive data: Length-bounded elementary formal systems
• The intrinsic complexity of language identification
• On the complexity of inductive inference
• Inductive inference of formal languages from positive data
• The structure of intrinsic complexity of learning
• Language identification in the limit
• Inductive inference of unbounded unions of pattern languages from positive data

This page was built for publication: Ordinal mind change complexity of language identification