A Machine-Independent Theory of the Complexity of Recursive Functions

Cited in

(only showing first 100 items - show all)

U-shaped, iterative, and iterative-with-counter learning
Factorizing RSA keys, an improved analogue solution
Instability, complexity, and evolution
Uncontrollable computational growth in theoretical physics
Type 2 recursion theory
The basic theory of partial -recursive operators
Approximation to measurable functions and its relation to probabilistic computation
Lower bounds on degrees of game-theoretic structures
On the power of recursive optimizers
Saving the phenomena: Requirements that inductive inference machines not contradict known data
A note on the best-case complexity
Data representation and computational complexity
Complexity classes of provable recursive functions
Indexings of subrecursive classes
Hierarchy of complexity of computation of partial functions with values 0 and 1
Research in the theory of inductive inference by GDR mathematicians - A survey
Complexity of algorithms and computations
The independence of control structures in abstract programming systems
Theory construction in psychology: The interpretation and integration of psychological data
Two types of properties for complexity measures
Computational complexity of real functions
Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem
Learning in the presence of partial explanations
Aggregating inductive expertise on partial recursive functions
The complexity types of computable sets
Diagonalization, uniformity, and fixed-point theorems
The extent and density of sequences within the minimal-program complexity hierarchies
Closure operations on measures of computational complexity
Augmented loop languages and classes of computable functions
The non-renamability of honesty classes
Complexity classes of partial recursive functions
The computational complexity of program schemata
An operator embedding theorem for complexity classes of recursive functions
Polynomial and abstract subrecursive classes
On the density of honest subrecursive classes
Nonexistence of program optimizers in several abstract settings
On computational reducibility
Complexity-class-encoding sets
``Natural properties of flowchart step-counting measures
Some natural properties of strong-identification in inductive inference
On the inference of optimal descriptions
Some applications of the McCreight-Meyer algorithm in abstract complexity theory
On splitting recursive sets
The complexity of total order structures
Some lowness properties and computational complexity sequences
Finite approximate approach to the study of the complexity of recursive predicates
Sequential fuzzy system identification
Complexity properties of recursively enumerable sets and sQ-completeness
Learning with refutation
Forecasting errors and bounded rationality: An example
On average time hierarchies
A universal cellular automaton in quasi-linear time and its S-m-n form
Computability, complexity and economics
On speedable and levelable vector spaces
Characterizing language identification by standardizing operations
On recursive bounds for the exceptional values in speed-up
Program size restrictions in computational learning
Computational complexity of functions
Learning in the presence of inaccurate information
On aggregating teams of learning machines
Learning-theoretic perspectives of acceptable numberings
Kolmogorov numberings and minimal identification
Probabilistic language learning under monotonicity constraints
Learning how to separate.
Learning languages and functions by erasing
Language learning from texts: Degrees of intrinsic complexity and their characterizations
Inductive inference with additional information.
Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
Strategies for managing the structural and dynamic consequences of project complexity
Unconventional complexity measures for unconventional computers
Monoidal computer. III: A coalgebraic view of computability and complexity (extended abstract)
Classes of recursively enumerable sets and Q-reducibility
The complexity of the word problems for commutative semigroups and polynomial ideals
Learning classes of approximations to non-recursive functions.
The synthesis of language learners.
Incremental concept learning for bounded data mining.
Robust behaviorally correct learning.
Variants of iterative learning
Refutable language learning with a neighbor system.
On learning of functions refutably.
Intrinsic complexity of learning geometrical concepts from positive data
Robust learning -- rich and poor
Characterization of realizable space complexities
The intrinsic difficulty of recursive functions
Intensional Kleene and Rice theorems for abstract program semantics
On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings
Learning languages with decidable hypotheses
Subrecursive equivalence relations and (non-)closure under lattice operations
Degree structures of conjunctive reducibility
Bi-immunity over different size alphabets
Diophantine complexity
On computational complexity and honest polynomial degrees
Generality's price: Inescapable deficiencies in machine-learned programs
Results on memory-limited U-shaped learning
Intrinsic complexity of partial learning
Some natural conditions on incremental learning
Iterative learning from positive data and negative counterexamples
Learning multiple languages in groups
Variations on U-shaped learning
Multitape one-way nonwriting automata

This page was built for publication: A Machine-Independent Theory of the Complexity of Recursive Functions

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