Publicēti raksti (MII) / Published Articles

Permanent URI for this collection

https://dspace-dev.lu.lv/handle/7/239
LU Matemātikas un informātikas institūta personāla publicēti raksti.

Browse

Browsing Publicēti raksti (MII) / Published Articles by Subject "deterministic"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Comparing various concepts of function prediction. Part 2.
    (Latvia State University, 1975) Podnieks, Karlis
    Prediction: f(m+1) is guessed from given f(0), ..., f(m). Program synthesis: a program computing f is guessed from given f(0), ..., f(m). The hypotheses are required to be correct for all sufficiently large m, or with some positive frequency. These approaches yield a hierarchy of function prediction and program synthesis concepts. The comparison problem of the concepts is solved.
  • Thumbnail Image
    Item
    Comparing various types of limiting synthesis and prediction of functions
    (Latvia State University, 1974) Podnieks, Karlis
  • Thumbnail Image
    Item
    Inductive inference of recursive functions: complexity bounds
    (Springer Verlag, 1991) Freivalds, Rusins; Barzdins, Janis; Podnieks, Karlis
    This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference may vary between log n+o(log2n ) and an arbitrarily slow recursive function. If the result of the inference is an index in the numbering of the recursively enumerable class, then the complexity may go up to const-n. Additionally, effects previously found in the Kolmogorov complexity theory are discovered in the complexity of inductive inference as well.
  • Thumbnail Image
    Item
    Prediction of the next value of a function
    (1981) Podnieks, Karlis
    The following model of inductive inference is considered. Arbitrary set tau = {tau_1, tau_2, ..., tau_n} of n total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the set tau. Processing these values by some algorithm (a strategy) we try to predict f(m+1) from f(0), f(1), ..., f(m). Upper and lower bounds for average error numbers are obtained for prediction by using deterministic and probabilistic strategies.