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

finite automatoninductive inferenceprediction strategyrecursive functionTuring machine

Mathematics Subject Classification ID

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

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

(26)

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

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)