On the complexity of inductive inference

DOI10.1016/S0019-9958(86)80042-0zbMath0648.68090OpenAlexW2003520432MaRDI QIDQ3793755

Robert P. Daley, Carl H. Smith

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80042-0

zbMATH Keywords

inductive inferencecomplexity measurescomplexity of inferenceautomated learning systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computability and recursion theory (03D99)

Related Items

Intrinsic complexity of learning geometrical concepts from positive data ⋮ Ockham's razor, empirical complexity, and truth-finding efficiency ⋮ From learning in the limit to stochastic finite learning ⋮ Learning via queries in [+, <] ⋮ Mind change speed-up for learning languages from positive data ⋮ Simulating teams with many conjectures ⋮ On the intrinsic complexity of learning recursive functions ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ Taming teams with mind changes ⋮ Training digraphs ⋮ Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries ⋮ Resource restricted computability theoretic learning: Illustrative topics and problems ⋮ Trade-off among parameters affecting inductive inference ⋮ An average-case optimal one-variable pattern language learner ⋮ Ordinal mind change complexity of language identification ⋮ Induction by enumeration ⋮ On the inference of approximate programs ⋮ Language learning from texts: Degrees of intrinsic complexity and their characterizations ⋮ Training sequences