Inductive inference of recursive functions: complexity bounds

DOI10.1007/BFB0019358MaRDI QIDQ4560353zbMATH OpenOpenAlexFDO

Authors Karlis Podnieks, Rūsiņš Freivalds, Ja. M. Barzdin'

Publication date 11 December 2018

Published in Baltic Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0019358

zbMATH Keywords

inductive inferenceTuring machinefinite automatonrecursive functionprediction strategy

Mathematics Subject Classification ID

Computational learning theory (68Q32) Theory of numerations, effectively presented structures (03D45) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• scientific article; zbMATH DE number 2077145
• scientific article; zbMATH DE number 1960352
• Probabilistic inductive inference
• Inductive inference of recursive functions: qualitative theory
• On the power of probabilistic strategies in inductive inference

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3531360 (Why is no real title available?)
• scientific article; zbMATH DE number 3588020 (Why is no real title available?)
• scientific article; zbMATH DE number 3588047 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3360091 (Why is no real title available?)
• scientific article; zbMATH DE number 3415370 (Why is no real title available?)
• scientific article; zbMATH DE number 3420728 (Why is no real title available?)
• Language identification in the limit
• On the inference of Turing machines from sample computations

Cited in

(24)

• scientific article; zbMATH DE number 517033 (Why is no real title available?)
• Genetic Programming for Inductive Inference of Chaotic Series
• Application of kolmogorov complexity to inductive inference with limited memory
• scientific article; zbMATH DE number 841093 (Why is no real title available?)
• scientific article; zbMATH DE number 1966617 (Why is no real title available?)
• Learning all subfunctions of a function
• On the complexity of inferring functional dependencies
• scientific article; zbMATH DE number 2077145 (Why is no real title available?)
• On the intrinsic complexity of learning recursive functions
• Tradeoffs in the inductive inference of nearly minimal size programs
• scientific article; zbMATH DE number 3935022 (Why is no real title available?)
• scientific article; zbMATH DE number 1960352 (Why is no real title available?)
• Robust learning -- rich and poor
• On the complexity of inductive inference
• scientific article; zbMATH DE number 3855086 (Why is no real title available?)
• Learning with belief levels
• scientific article; zbMATH DE number 3859102 (Why is no real title available?)
• scientific article; zbMATH DE number 3930986 (Why is no real title available?)
• Learning recursive functions: A survey
• Amount of nonconstructivity in deterministic finite automata
• On learning of functions refutably.
• Mind change speed-up for learning languages from positive data
• scientific article; zbMATH DE number 4058896 (Why is no real title available?)
• Inductive inference of recursive functions: qualitative theory

This page was built for publication: Inductive inference of recursive functions: complexity bounds

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