scientific article; zbMATH DE number 3586480

zbMath0376.68027MaRDI QIDQ4153600

No author found.

Publication date: 1978

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithms in computer science (68W99) Computability and recursion theory (03Dxx)

Related Items

Cellular automata universality revisited, Memory limited inductive inference machines, Efficient unidimensional universal cellular automaton, Reflecting and self-confident inductive inference machines, Application of kolmogorov complexity to inductive inference with limited memory, Machine induction without revolutionary paradigm shifts, Simulating teams with many conjectures, Unnamed Item, Probabilistic language learning under monotonicity constraints, Effective category and measure in abstract complexity theory, Probabilistic inductive inference: A survey, Reductions among polynomial isomorphism types, On learning of functions refutably., Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Measuring the tameness of almost convex groups, Intrinsic complexity of learning geometrical concepts from positive data, On recursive bounds for the exceptional values in speed-up, Generality's price: Inescapable deficiencies in machine-learned programs, How rich is the structure of the intrinsic complexity of learning, Program size restrictions in computational learning, How to prove representation-independent independence results, Honest polynomial degrees and \(P=?NP\), Characterization of realizable space complexities, Learnability: Admissible, co-finite, and hypersimple languages, Learning in the presence of inaccurate information, Unnamed Item, Unnamed Item, Probability and plurality for aggregations of learning machines, More complicated questions about maxima and minima, and some closures of NP, Semantics vs syntax vs computations: Machine models for type-2 polynomial-time bounded functionals, Elementary realizability, On the learnability of vector spaces, A complexity measure for data flow models, Infinitary self-reference in learning theory, Spatial/kinematic domain and lattice computers, Index sets and presentations of complexity classes, On aggregating teams of learning machines, Query languages for bags and aggregate functions, Generalization versus classification, Prudence in vacillatory language identification, Learning-theoretic perspectives of acceptable numberings, On the relative sizes of learnable sets, Informal versus formal mathematics, On Goles' universal machines: a computational point of view, Indexings of subrecursive classes, On the intrinsic complexity of learning recursive functions, The \(\exists^*\forall^*\) part of the theory of ground term algebra modulo an AC symbol is undecidable., The independence of control structures in abstract programming systems, A note on A.E. h-complex functions, Remarks on recursion versus diagonalization and exponentially difficult problems, Independence results in computer science?, Polynomials and linear transformations, A uniform method for proving lower bounds on the computational complexity of logical theories, Learning how to separate., Learning and extending sublanguages, Learning by switching type of information., Learning languages from positive data and negative counterexamples, Probabilistic and team PFIN-type learning: General properties, Taming teams with mind changes, Undecidability and incompleteness in classical mechanics, On p-creative sets and p-completely creative sets, Learning in the presence of partial explanations, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Anomalous learning helps succinctness, Monotonic and dual monotonic language learning, Iterative learning from positive data and negative counterexamples, Effective category and measure in abstract complexity theory, Learning multiple languages in groups, Deciding Koopman's qualitative probability, The complexity types of computable sets, Measure, category and learning theory, A note on the complexity of program evaluation, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets, Diagonalization, uniformity, and fixed-point theorems, Computation, hypercomputation, and physical science, Minimum-complexity pairing functions, Defining effectiveness using finite sets. A study on computability, Program Self-reference in Constructive Scott Subdomains, Program self-reference in constructive Scott subdomains, A relation between correctness and randomness in the computation of probabilistic algorithms, Variations on U-shaped learning, Decision problems of object histories, The functions of finite support: a canonical learning problem, Comparison of identification criteria for machine inductive inference, Characterizing programming systems allowing program self-reference, Unnamed Item, Almost-everywhere complexity hierarchies for nondeterministic time, Isotopy in surface complexes from the computational viewpoint, Set-driven and rearrangement-independent learning of recursive languages, Rice and Rice-Shapiro Theorems for transfinite correction grammars, Bandwidth contrained NP-complete problems, Trade-off among parameters affecting inductive inference, On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines, In Scott-Strachey style denotational semantics, parallelism implies nondeterminism, Ordinal mind change complexity of language identification, The complexity of the word problems for commutative semigroups and polynomial ideals, On the inductive inference of recursive real-valued functions, Grammar directed gödel numberings, Maximal machine learnable classes, The synthesis of language learners., On a generalized notion of mistake bounds, Learning by the process of elimination, On the complexity-relativized strong reducibilities, Acceptable functional programming systems, Strong noncomputability of random strings, One-sided error probabilistic inductive inference and reliable frequency identification, On the inference of approximate programs, Composition is almost (but not quite) as good as \(s-1-1\), A universal cellular automaton in quasi-linear time and its S-m-n form, Language learning from texts: Degrees of intrinsic complexity and their characterizations, Training sequences