Publicēti raksti (MII) / Published Articles
Permanent URI for this collection
LU Matemātikas un informātikas institūta personāla publicēti raksti.
Browse
Browsing Publicēti raksti (MII) / Published Articles by Issue Date
Now showing 1 - 20 of 26
Results Per Page
Sort Options
- ItemOn the reducibility of function classes(Latvia State University, 1972) Podnieks, KarlisN – the set of all natural numbers, F – the set of all total functions N→N, A, B<=F. We say that A is m-reducible to B (A<=m B), iff there is a recursive operator M such that f in A, iff M(f) in B for all f in F. Similarly, 1-reducibility, tt-, btt-, 1tt- and Turing reducibility can be introduced. Table of contents. 1. Introduction. 2. Definitions of reducibilities and their simplest properties. 3. m-reducibility and the arithmetical hierarchy. 4. m-reducibility on SIGMA_1^fn. 5. Special classes. 6. Comparing various reducibilities on SIGMA_1^fn. 7. Notes on reducibilities of classes of sets.
- ItemTowards a theory of inductive inference(1973) Barzdins, Janis; Podnieks, Karlis
- ItemComparing various concepts of function prediction. Part 1.(Latvia State University, 1974) Podnieks, KarlisPrediction: 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.
- ItemOn speeding up synthesis and prediction of functions(Latvia State University, 1974) Barzdins, Janis; Kinber, Efim; Podnieks, Karlis
- ItemOn computation in the limit by non-deterministic Turing machines(Latvia State University, 1974) Freivalds, Rusins; Podnieks, Karlis
- ItemOn computation in the limit by non-deterministic Turing machines(Scientific Proceedings of Latvia State University, 1974) Freivalds, Rūsiņš; Podnieks, Karlis
- ItemComparing various types of limiting synthesis and prediction of functions(Latvia State University, 1974) Podnieks, Karlis
- ItemThe double-incompleteness theorem(Latvia State University, 1975) Podnieks, KarlisLet T be a theory, Q - a metatheory of T. Under certain conditions there exist T-undecidable sentences for which this undecidability cannot be proved in Q. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
- ItemComparing various concepts of function prediction. Part 2.(Latvia State University, 1975) Podnieks, KarlisPrediction: 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.
- ItemThe double-incompleteness theorem(Stiinca, Kishinev, 1976) Podnieks, KarlisLet T be a strong enough theory, and M - its metatheory, both are consistent. Then there is a closed arithmetical formula H that is undecidable in T, but one cannot prove in M neither that H is T-unprovable, nor that H is T-unrefutable. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
- ItemProbabilistic program synthesis(Latvia State University, 1977) Podnieks, KarlisThe following model of inductive inference is considered. Arbitrary numbering tau = {tau_0, tau_1, tau_2, ... } of total functions N->N is fixed. A "black box" outputs the values f(0), f(1), ..., f(m), ... of some function f from the numbering tau. Processing these values by some algorithm (a strategy) F we try to identify a tau-index of f (i.e. a number n such that f = tau_n). Strategy F outputs hypotheses h_0, h_1, ..., h_m, ... If lim h_m = n and tau_n = f, we say that F identifies in the limit tau-index of f. The complexity of identification is measured by the number of mindchanges, i.e. by F_tau(f) = card{m | h_m <> h_{m+1} }. One can verify easily that for any numbering tau there exists a deterministic strategy F such that F_tau(tau_n) <= n for all n. This estimate is exact. In the current paper the corresponding exact estimate ln n + o(log n) is proved for probabilistic strategies.
- ItemComputational complexity of prediction strategies(Latvia State University, 1977) Podnieks, KarlisThe value f(m+1) is predicted from given f(1), ..., f(m). For every enumeration T(n, x) there is a strategy that predicts the n-th function of T making no more than log2(n) errors (Barzdins-Freivalds). It is proved in the paper that such "optimal" strategies require 2^2^cm time to compute the m-th prediction (^ stands for expoentiation).
- ItemAn Exhaustive Search Algorithm for Finding Hamiltonian Cycles(EIK,Elektronische Informationsverarbeitung und Kybernetik, Universität Trier, Akademie Verlag, 1980) Zeps, DainisThe paper suggests an exhaustive search algorithm for finding Hamiltonian circuits in an undirected graph based on depth-first search and working successfully on sparse graphs. The method is based on the idea not to search all palms in the graphs but only those which are not branched. Tutte's 46 vertices graph searching took less than 3 minutes on EC- 1022 computer.
- ItemPrediction of the next value of a function(1981) Podnieks, KarlisThe 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.
- ItemPlatonism, intuition and the nature of mathematics(Bulgarian Academy of Sciences, Sofia, 1988) Podnieks, KarlisPlatonism is an essential aspect of mathematical method. Mathematicians are learned ability " t o l i v e " in the "world" of mathematical concepts. Here we have the main source of the creative power of mathematics, and of its surprising efficiency in natural sciences and technique. In this way, "living" (sometimes - for many years) in the "world"of their concepts and models, mathematicians are learned to draw a maximum of conclusions from a minimum of premises. Fixed system of basic principles is the distinguishing property of every mathematical theory. Mathematical model of some natural process or technical device is essentially a f i x e d m o d e l which can be investigated independently of its "original".
- ItemInductive inference of recursive functions: complexity bounds(Springer Verlag, 1991) Freivalds, Rusins; Barzdins, Janis; Podnieks, KarlisThis 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.
- ItemMDA: correctness of model transformations. Which models are schemas?(IOS Press, 2005) Podnieks, KarlisHow to determine, is a proposed model transformation correct, or not? In general, the answer may depend on the model semantics. Of course, a model transformation is “correct”, if we can extend it to a “correct” instance data transformation. Where should model semantics be defined? Assume, model syntax and semantics are defined in the same meta-model. Then, how to separate syntax from semantics? The answer could be the definition of model schemas proposed in the paper.
- ItemNonlinear Spectra: the Neumann Problem(Vilnius Gediminas Technical University, 2009) Gritsans, A.; Sadyrbaev, F.
- ItemOrnamental sign language in the first order tracery belts(Prespacetime Journal, 2010) Tenisons, Modris; Zeps, DainisWe consider an ornamental sign language of first order where principles of sieve displacement, of asymmetric building blocks as a base of ornament symmetry, color exchangeability and side equivalence principles work. Generic aspects of sieve and a genesis of ornamental pattern and ornament signs in it are discussed. Hemiolia principle for ornamental genesis is introduced. The discoverer of most of these principles were artist Modris Tenisons [4, 5, 6, 7 (refs. 23, 24), 8 (ref. 65)]. Here we apply a systematical research using simplest mathematical arguments. We come to conclusions that mathematical argument in arising ornament is of much more significance than simply symmetries in it as in an image. We are after to inquire how ornament arises from global aspects intertwined with these local. We raise an argument of sign’s origin from code rather from image, and its eventual impact on research of ornamental patterns, and on research of human prehension of sign and its connection with consciousness.
- ItemUML Style Graphical Notation(Springer, 2010) Bārzdiņš, Jānis; Bārzdiņš, Guntis; Čerāns, Kārlis; Liepiņš, Renārs; Sproģis, Artūrs