On the power of inductive inference from good examples
From MaRDI portal
Publication:1210543
DOI10.1016/0304-3975(93)90353-UzbMath0821.68110MaRDI QIDQ1210543
E. B. Kinber, Rolf Wiehagen, Rūsiņš Freivalds
Publication date: 30 August 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
Characterizing language identification by standardizing operations ⋮ Constructing simply recursive programs from a finite set of good examples ⋮ On the data consumption benefits of accepting increased uncertainty ⋮ A model of interactive teaching ⋮ Learning recursive functions: A survey ⋮ Measuring teachability using variants of the teaching dimension ⋮ Developments from enquiries into the learnability of the pattern languages from positive data ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ When unlearning helps ⋮ Massive online teaching to bounded learners ⋮ Learning mixtures of spherical gaussians ⋮ Low-weight halfspaces for sparse boolean vectors ⋮ Learnability of DNF with representation-specific queries ⋮ Can theories be tested? ⋮ Making evolution rigorous ⋮ On the convergence of the Hegselmann-Krause system ⋮ Is privacy compatible with truthfulness? ⋮ Differentially private data analysis of social networks via restricted sensitivity ⋮ Characterizing the sample complexity of private learners ⋮ Barriers in cryptography with weak, correlated and leaky sources ⋮ On the possibilities and limitations of pseudodeterministic algorithms ⋮ Evasiveness through a circuit lens ⋮ The garden-hose model ⋮ Space-bounded communication complexity ⋮ Towards an optimal query efficient PCP? ⋮ A characterization of approximation resistance for even k-partite CSPs ⋮ On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction ⋮ On the power of many one-bit provers ⋮ Approaching utopia ⋮ Learning and incentives in user-generated content ⋮ Welfare maximization and the supermodular degree ⋮ Reachability in graph timelines ⋮ Runtime guarantees for regression problems ⋮ An energy complexity model for algorithms ⋮ Streaming computations with a loquacious prover ⋮ Adversary lower bound for the k-sum problem ⋮ Stronger methods of making quantum interactive proofs perfectly complete ⋮ Active self-assembly of algorithmic shapes and patterns in polylogarithmic time ⋮ An equational approach to secure multi-party computation ⋮ Publicly verifiable proofs of sequential work ⋮ On the power of nonuniformity in proofs of security ⋮ Fast reductions from RAMs to delegatable succinct constraint satisfaction problems ⋮ Resource-based corruptions and the combinatorics of hidden diversity ⋮ Time hierarchies for sampling distributions ⋮ Properties and applications of boolean function composition ⋮ Pseudo-partitions, transversality and locality ⋮ Competing provers protocols for circuit evaluation ⋮ Catch them if you can ⋮ Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints ⋮ Robust optimization in the presence of uncertainty ⋮ Sorting noisy data with partial information ⋮ New affine-invariant codes from lifting ⋮ H-wise independence ⋮ Sparse extractor families for all the entropy ⋮ On the power of conditional samples in distribution testing ⋮ Non-U-shaped vacillatory and team learning ⋮ On the power of inductive inference from good examples ⋮ Teaching randomized learners with feedback ⋮ On the learnability of recursively enumerable languages from good examples ⋮ Recent Developments in Algorithmic Teaching ⋮ Polynomial-time inference of arbitrary pattern languages ⋮ The teaching size: computable teachers and learners for universal languages ⋮ The complexity of universal text-learners.
Cites Work
- Comparison of identification criteria for machine inductive inference
- Polynomial-time inference of arbitrary pattern languages
- Research in the theory of inductive inference by GDR mathematicians - A survey
- On the power of inductive inference from good examples
- Inductive Inference and Computable One‐One Numberings
- Probabilistic Versus Deterministic Inductive Inference in Nonstandard Numberings
- Toward a mathematical theory of inductive inference
- Monadic Elementary Formal Systems
- Some decidability results on grammatical inference and complexity
- Language identification in the limit
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
