Two decades of applied Kolmogorov complexity.

P. Vitányi   ; M. Li

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 43 (1988) no. 6

Bibliographie

[1] Aanderaa S. O., “On $k$-tape versus $(k-1)$-tape real-time computation”, Complexity of Computation, SIAM-AMS Proc., VII, Providence, R.I., 1974, 75–96 | MR

[2] Adleman L., Time, space, and randomness, Report MIT/LCS/79/TM-131, March 1979, Massachusetts Institute of Technology, Laboratory for Computer Science

[3] Aho A. V., J. E. Hopcroft, J. D. Ullman, “Time and tape complexity of pushdown automaton languages”, Information and Control, 13 (186–206), 1968 | Zbl

[4] Aleksandrov P. S., “A few words on A. N. Kolmogorov”, Russian Math. Survey, 38 (1983), 5–7 | DOI | MR | Zbl

[5] Allender E., O. Watanabe, “Kolmogorov complexity and degrees of tally sets”, Proceeding 3rd Conference on Structure in Complexity Theory, Springer LNCS, 1988

[6] Barzdin Y. M., “Complexity of programs to determine whether natural numbers not greater than $n$ belong to a recursively enumerable set”, Soviet Math. Dokl., 9 (1968), 1251–1254 | Zbl

[7] Beame P., “Limits on the power of concurrent-write parallel machines”, 18th ACM Symp. on Theory of Computing, 1986

[8] Bennett C. H., On random and hard to describe numbers, Mathematics Tech. Rept. RC 7483 (#32272), May 1979, IBM Watson Research Center, Yorktown Heights

[9] Bennett C. H., On the logical “depth” of sequences and the reducibilities to random sequences, Tech. Rept. February 1981, IBM Watson Research Center, Yorktown Heights

[10] Bennett C. H., “Dissipation, information, computational complexity and the definition of organization”, Emerging syntheses in Science, Proceedings of the Founding Workshops of the Santa Fe Institute, ed. D. Pines, 1985, 297–313

[11] Berman L., J. Hartmanis, “On isomorphisms and density of NP and other complete sets”, SIAM J. on Computing, 6 (1977), 305–327 | DOI | MR

[12] Blumer A., A. Ehrenfeucht, D. Haussler, M. Warmuth, “Classifying Learnable Geometric Concepts With the Vapnik-Chervonenkis Dimension”, Proceedings 18th ACM Symp. on Theory of Computing, 1986

[13] Bogolyubov N. N., B. V. Gnedneko, S. L. Sobolev, “Andrei Nikolaevich Kolmogorov (on his eightieth birthday)”, Russian Math. Surveys, 38 (1983), 9–27 | DOI | Zbl

[14] Book R., P. Orponen, D. Russo, O. Watanabe, “On exponential lowness”, SIAM J. Computing (to appear)

[15] Borodin A., M. J. Fischer, D. G. Kirkpatrick, N. A. Lynch, M. Tompa, “A time-space tradeoff for sorting and related non-oblivious computations”, 20th IEEE Symposium on Foundations of Computer Science, 1979

[16] Borodin A., S. Cook, “A time-space tradeoff for sorting on a general sequential model of computation”, 12th ACM Symp. on Theory of Computing, 1980

[17] Carnap R., Logical Foundations of Probability, University of Chicago Press, Chicago, Ill., 1950 | MR | Zbl

[18] Chaitin G. J., “On the length of programs for computing finite binary sequences”, J. Assoc. Comp. Mach., 13 (1966), 547–569 | MR | Zbl

[19] Chaitin G. J., “Information-theoretic limitations of formal systems”, J. Assoc. Comp. Mach., 21 (1974), 403–424 | MR | Zbl

[20] Chaitin G. J., “A theory of program size formally identical to information theory”, J. Assoc. Comp. Mach., 22 (1975), 329–340 | MR | Zbl

[21] Chaitin G. J., “Randomness and mathematical proof”, May 1975, Scientific American, 232, 47–52 | MR

[22] Chaitin G. J., “Information-theoretic characterizations of recursive infinite strings”, Theor. Comput. Sci., 2 (1976), 45–48 | DOI | MR | Zbl

[23] Chaitin G. J., “Algorithmic Information Theory”, IBM J. Res. Dev., 21 (1977), 350–359 | MR | Zbl

[24] Chaitin G. J., “Toward a mathematical definition of “life””, The Maximal Entropy Formalism, ed. M. Tribus, MIT Press, Cambridge, Mass., 1979, 477–498 | MR

[25] Champernowne D. G., “The construction of decimals normal in the scale of ten”, J. London Math. Soc., 8 (1933), 254–260 | DOI

[26] Chrobak M., “Hierarchies of one-way multihead automata languages”, 12th ICALP, Springer LNCS, 194, 1985, 101–110 ; Theoretical Computer Science, 48 (1986), 153–181 | MR | Zbl | DOI | MR | Zbl

[27] Chrobak M., M. Li, “$k+1$ heads are better than $k$ for PDAs”, 21th IEEE FOCS, 1986, 361–367

[28] Church A., “On the concept of a random sequence”, Bull. Amer. Math. Soc., 46 (1940), 130–135 | DOI | MR

[29] Cook S., S. Aanderaa, “On the minimum computation time of functions”, Trans. AMS, 142 (1969) ; Kuk S. A., Aanderaa S. O., “O minimalnom vremeni vychisleniya funktsii”, Kib. sb., N.S., no. 8, 168–200 | DOI | MR | Zbl

[30] Cook S. A., “Characterizations of pushdown machines in terms of time-bomded computers”, JACM, 13 (1971), 4–18 ; Kuk S., “Kharakteristika magazinnykh avtomatov v terminakh vychislitelei, ogranichennykh vo vremeni”, Slozhnost vychislenii i algoritmov, Sbornik perevodov, eds. V. A. Kozmididadi, A. N. Maslov, N. V. Petri, Mir, M., 1974, 266–288 | DOI | MR

[31] Cuykendall R. R., Kolmogorov information and VLSI lower bounds, Ph. D. Thesis, Dec. 1984, University of California, Los Angeles

[32] Daley R. P., “On the inference of optimal descriptions”, Theoretical Computer Science, 4 (1977), 301–309 | DOI | MR

[33] Dietzfelbinger M., Lower bounds on computation time for various models in computational complexity theory, Ph. D. Thesis, University of Illinois, Chicago, 1987

[34] Duris P., Z. Galil, “Two tapes are better than one for nondeterministic machines”, 14th STOC, 1982

[35] Fich F., P. Ragde, A. Wigderson, “Relations between concurrent-write models of parallel computation”, Proc. 3rd ACM Symp. on Principles of Distributed computing, 1984

[36] Floyd R., “Review 14”, Comput. Rev., 9 (1968), 280 | MR

[37] Galil Z., J. Seiferas, “Time-space optimal matching”, Proc. 13th ACM Symposium on Theory of Computing, 1981

[38] Galil Z., R. Kannan, E. Szemeredi, “On nontrivial separators for $k$-page graphs and simulations by nondeterministic one-tape Turing machines”, Proc. 18th ACM STOC, 1986, 39–49 | MR

[39] Grigorchuk R. I., “A connection between algorithmic problems and entropy characteristics of groups”, Soviet Math. Dokl., 32 (1985), 356–360

[40] Gacs P., “On the symmetry of algorithmic information”, Soviet Math. Dokl., 15 (1974), 1477 | MR | Zbl

[41] Gacs P., “Randomness and probability-complexity of description”, Encyclopedia of Statistical Sciences, ed. Kotz-Johnson, John Wiley Sons, 1986, 551–555 | MR

[42] Harrison M. A., O. H. Ibarra, “Multi-head and multi-tape pushdown automata”, Information and Control, 13 (1968), 433–470 | DOI | MR | Zbl

[43] Hartmanis J., R. E. Stearns, “On the computational complexity of algorithms”, Trans. Amer. Math. Soc., 117 (1969), 285–306 ; Khartmanis Dzh., Stirnz R. E., “O vychislitelnoi slozhnosti algoritmov”, Kib. sb., N.S., no. 4, Mir, M., 1967, 57–85 | DOI | MR

[44] Hartmanis J., “Generalized kolmogorov complexity and the structure of feasible computations”, Proc. 24th IEEE FOCS, 1983, 439–445

[45] Hartmanis J., L. Hemachandra, “On sparse oracles separating feasiblecomplexity classes”, Proc. 3rd Symposium on Theoretical Aspects of Computer Science, Springer LNCS, 210, 1986, 321–333 | MR | Zbl

[46] Haussler D., N. Littlestone, M. Warmuth, Expected mistake bounds for on-line learning algorithms, Manuscript, 1988

[47] Heide Meyer auf der, A. Wigderson, “The complexity of parallel sorting”, 17th ACM Symp. on Theory of computing, 1985

[48] Hemachandra L., Can $\mathrm{P}$ and $\mathrm{NP}$ manufacture randomness?, Tech. Rept. TR86-795, December 1986, Dept. Computer Science, Cornell University

[49] Hopcroft J. E., J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979 | MR | Zbl

[50] Huynh D. T., Non-uniform complexity and the randomness of certain complete languages, Techn. Rept. TR 85-34,December, 1985, Iowa State University

[51] Huynh D. T., “Resource-bounded Kolmogorov complexity of hard languages”, Proc. 1st Structure in Complexity Theory Conf., Springer LNCS, 1986 | MR

[52] Ibarra O. H., “On two-way multihead automata”, JCSS, 7 (1973), 28–37 | MR

[53] Ibarra O. H., C. E. Kim, “On 3-head versus 2 head finite automata”, Acta Infomatica, 4 (1975), 193–200 | DOI | MR | Zbl

[54] Israeli A., S. Moran, Private communication

[55] Kearns M., M. Li, L. Pitt, L. Valiant, “Recent results on Boolean concept learning”, Machine Learning, ed. T. Mitchell (to appear)

[56] Kearns M., M. Li, L. Pitt, L. Valiant, “On the learnability of Boolean formulae”, Proc. 19th ACM Symp. on Theory of Computing, 1987

[57] Knuth D., Semi-Numerical Algorithms, Second edition, Addison-Wesley, 1981 ; Knut D., Iskusstvo programmirovaniya. T. 2. Poluchislennye algoritmy, Mir, M., 1977, 724 pp. | Zbl | Zbl

[58] Knuth D. E., “Big Omicron and big Omega and big Theta”, SIGACT News, 8:2 (1976), 18–24 | DOI

[59] Ko Ker-I, Resource-bounded program-size complexity and pseudorandom sequences, Department of computer science, University of Houston, 1983

[60] Kolmogorov A. N., Grundbegriffe der Wahrscheinlichkeitsrechnung, Berlin, 1933; Osnovnye Poniatija Teorii Verojatnostej, 2nd Russian Edition, Nauka, Moscow, 1974; Kolmogorov A. N., Osnovnye ponyatiya teorii veroyatnostei, Gl. red. obschetekhn. lit. i nomografii, M.–L., 1936; Наука, М., 1974, 119 с.

[61] Kolmogorov A. N., “On tables of random numbers”, Sankhya, The Indian Journal of Statistics, Series A 25, 1963, 369–376 ; Kolmogorov A. N., “O tablitsakh sluchainykh chisel”, V kn.: A. N. Kolmogorov, Teoriya informatsii i teoriya algoritmov, Nauka, M., 1987, 204–213 | MR | Zbl | MR

[62] Kolmogorov A. N., “Three approaches to the quantitative definition of information”, Problems in Information Transmission, 1:1 (1965), 1–7 | MR

[63] Kolmogorov A. N., “Logical basis for information theory and probability theory”, IEEE Trans. on Information Theory, IT-14.5 (1968), 662–664 | DOI | MR

[64] Kolmogorov A. N., “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Mathematical Surveys, 38 (1983), 29–40 | DOI | MR | Zbl

[65] Lambalgen M. van, “Von Mises' definitionf of random sequences reconsidered”, Journal of Symbolic Logic, 52 (1987), 725–755 | DOI | MR | Zbl

[66] Lambalgen M. van, Random Sequences, Ph. D. Thesis, Universiteit van Amsterdam, Amsterdam, 1987

[67] Laplace P. S., A Philosophical Essay on Probabilities, Dover, New York, 1819 | MR

[68] Levin L. A., “Universal search problems”, Problems in Information Transmission, 9 (1973), 265–266 | MR

[69] Levin L. A., “Laws of information conservation (non-growth) and aspects of the foundation of probability theory”, Problems in Information Transmission, 10 (1974), 206–210 | MR

[70] Levin L. A., Do chips need wires?, Manuscript/NSF proposal MCS-8304498, Computer Science Department, Boston University, 1984

[71] Levin L. A., “Randomness conservation inequalities; information and independence in mathematical theories”, Information and Control, 61 (1984), 15–37 | DOI | MR | Zbl

[72] Li M., P. M. B. Vitanyi, “Formal language theory by Kolmogorov complexity” (to appear)

[73] Li M., Lower Bounds in Computational Complexity, Ph.D. Thesis, Report TR-85-663, March 1985, Computer Science Department, Cornell University

[74] Li M., “Simulating two pushdowns by one tape in $O(n^{**}1.5(\log n)^{**}0.5)$”, 26th Annual IEEE Symposium on the Foundations of Computer Science, 1985

[75] Li M., Y. Yesha, “String-matching cannot be done by 2-head 1-way deterministic finite automata”, Information Processing Letters, 22 (1986), 231–235 | DOI | MR | Zbl

[76] Li M., Y. Yesha, “New lower bounds for parallel computation”, 18th ACM Symposium on Theory of Computing, 1986

[77] Li M., L. Longpré, P. M. B. Vitányi, “On the power of the queue”, Structure in Complexity Theory, Lecture Notes in Computer Science, 1986, 219–233 | MR | Zbl

[78] Li M., P. M. B. Vitányi, “Tape versus queue and stacks: The lower bounds”, Information and Computation, 11 (1988) | MR

[79] Lipton R., R. SedgewickL, “ower bounds for VLSI”, 13th ACM Symp. on Theory of computing, 1981

[80] Littlestone N., “Learning quickly when irrelevant attributes abound: A new linear threshold algorithm”, Proc. 28th IEEE Symposium on Foundations of Computer Science, 1987

[81] Littlewood J. E., “The dilemma of probability theory”, Littlewood's Miscellany, Revised edition, ed. B. Bollobas, Cambridge University Press, 1986, 71–73

[82] Longpré L., Time, space-bounded Kolmogorov complexity (To be changed), Ph. D. Thesis, Computer Science Department, Cornell University, 1986 | Zbl

[83] Loveland D. W., “A new interpretation of von Mises'concept of a random sequence”, Z. Math. Logik und Grundlagen Math., 12 (1966), 279–294 | DOI | MR | Zbl

[84] Loveland D. W., “A variant of the Kolmogorov concept of complexity”, Information and Control, 15 (1969), 510–526 | DOI | MR | Zbl

[85] Maass W., “Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines”, Trans. Amer. Math. Soc., 292 (1985), 675–693 | DOI | MR | Zbl

[86] Maass W., G. Schnitger, “An optimal lower bound for Turing machines with one work tape and a two-way input tape”, Structure in Complexity Theory, Lecture Notes in Computer Science, 223, 1986, 249–264 | MR | Zbl

[87] Maass W., G. Schnitger, E. Szemeredi, “Two tapes are better than one for off-line Turing machines”, Proc. 19th ACM Symposium on Theory of Computing, 1987

[88] Martin-Lof P., “The definition of random sequences”, Information and Control, 9 (1966), 602–619 | DOI | MR

[89] Metropolis N. C., G. Reitweiser, J. von Neumann, “Statistical treatment of values of the first 2,000 decimal digits of $e$ and $\pi$ calculated on the ENIAC”, John von Neumann, Collected Works, Vol. V., ed. A. H. Traub, MacMillan, New York, 1963

[90] Minsky M. L., “Problems of Formulation for Artificial Intelligence”, Mathermatical Problems in the Biological Sciences, Proceedings of Symposia in Applied Mathematics, XIV, ed. R. E. Bellman, American Mathematical Society, Providence, R.I., 1962, 43

[91] Mises R. von, Probability, Statistics and Truth, MacMillan, New York, 1939 ; Reprint, Dover, 1981 ; Mizes R., Veroyatnost i statistika, Gos. izd-vo, M.–L., 1930 | MR | Zbl

[92] Miyano S., “A hierarchy theorem for multihead stack-counter automata”, Acta Informatica, 17 (1982), 63–67 | DOI | MR | Zbl

[93] Miyano S., “Remarks on multihead pushdown automata and multihead stack automata”, Journal of Computer and System Sciences, 27 (1983), 116–124 | DOI | MR | Zbl

[94] Monien B., “Transformational methods and their application to complexity problems”, Acta Informatica, 6 (1976), 95–108 ; Corrigenda, Acta Inform., 8 (1977), 383–384 | DOI | MR | Zbl | DOI | MR | Zbl

[95] Monien B., “Two-way multihead automata over a one-letter alphabet”, RAIRO Inform. Theoret., 14 (1980), 67–82 | MR | Zbl

[96] Nelson C. G., One-way automata on bounded languages, TR14-76, July 1976, Harvard University

[97] Neumann, J. von, “Various techniques used in connection with random digits”, John von Neumann, Collected Works, Vol. V., ed. A. H. Traub, MacMillan, New York, 1963

[98] Obituary, “Mr. Andrei Kolmogorov-Giant of mathematics”, Times, 1987, October 26

[99] Parberry I., A complexity theory of parallel computation, Ph. D. Thesis, Warwick University, 1984

[100] Paterson M., M. Fisher, A. Meyer, “An improved overlap argument for on-line multiplication”, Complexity of Computation, SIAM-AMS Proc., v. VII, 7, Providence, R.I., 1974, 97–111 | MR

[101] Paturi R., J. Simon, “Lower bounds on the time of probabilistic on-line simulations”, Proc. 24th IEEE FOCS, 1983, 343

[102] Paul W., “Kolmogorov's complexity and lower bounds”, Proc. 2nd International Conference on Fundamentals of Computation Theory (September 1979) | MR

[103] Paul W., “On heads versus tapes”, Theoretical Computer Science, 28 (1984), 1–12 | DOI | MR | Zbl

[104] Paul W. J., J. I. Seiferas, J. Simon, “An information theoretic approach to time bounds for on-line computation”, J. Computer and System Sciences, 23 (1981), 108–126 | DOI | MR | Zbl

[105] Paul W. J., “On-line simulation of $k+1$ tapes by $k$ tapes requires nonlinear time”, Information and Control, 1982, 1–8 | DOI | MR | Zbl

[106] Popper K. R., The Logic of Scientific Discovery, University of Toronto Press, Toronto, 1959 | MR

[107] Quinlan J., R. Rivest, Inferring decision trees using the minimum description length principle, Draft, MIT Lab. for Computer Science, Cambridge, Mass., 1987

[108] Rabin M. O., “Real-time computation”, Israel J. of Math., 1 (1963), 203–211 ; Rabin M. O., “Vychisleniya v realnoe vremya”, Problemy matematicheskoi logiki: Slozhnost algoritmov i klassy vychislimykh funktsii, Sb. perev., eds. V. A. Kozmidiadi, A. A. Muchnik, Mir, M., 1970, 156–167 | DOI | MR | Zbl | MR

[109] Reisch S., G. Schnitger, “Three applications of Kolmogorov-complexity”, Proc. 23rd IEEE FOCS, 1982, 45–52 | MR

[110] Rissanen J., “Modeling by the shortest data description”, Automatica, 14 (1978), 465–471 | DOI | Zbl

[111] Rivest R., Learning Decision-Lists, Unpublished manuscript, December, 1986, MIT Lab. of Computer Science

[112] Rogers H. Jr., Theory of Recursive Functions and effective computability, McGraw-Hill, New York, 1967 ; Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972, 624 pp. | MR | Zbl | MR

[113] Rosenberg A., Nomvriting extensions of finite automata, Ph. D. Thesis, Harvard University, 1965

[114] Rosenberg A., “On multihead finite automata”, IBM J. Res. Develop., 10 (1966), 388–394 | MR | Zbl

[115] Schnorr C. P., “Eine Bemerkung zum Begriff der zufällige Folge”, Z. Wahrsch. undverw. Geb., 14 (1969–1970), 27–35 | DOI | MR | Zbl

[116] Schnorr C. P., “Zufälligkeit und Wahrscheinlichkeit; Eine algorithmische Begründung der Wahrscheinlichkeitstheorie”, Lecture Notes in Mathematics, Springer Verlag, Berlin, 1971 | MR | Zbl

[117] Seiferas J., Nondeterministic time and space complexity classes, Ph. D. Thesis, MIT, 1974

[118] Seiferas J., “Relating refined space complexity classes”, J. of Computer and System Sciences, 14 (1977), 100–129 | DOI | MR | Zbl

[119] Seiferas J., “The symmetry of information, and An application of the symmetry of information”, Notes, August 1985, Computer Science Dept, University of Rochester

[120] Shannon C. E., W. Weaver, The Mathematical theory of Communication, Univ. Illinois Press, Urbana, Ill., 1949 | MR | Zbl

[121] Sipser M., “A complexity theoretic approach to randomness”, Proceedings 15th ACM Symposium on Theory of Computing, 1983

[122] Solomonoff R. J., A preliminary report on a general theory of inductive inference, Tech. Rept. ZTB-138, November 1960, Zator Company, Cambridge, Mass.

[123] Solomonoff R. J., “A formal theory of inductive inference. Part 1; Part 2”, Information and Control, 7 (1964), 1–22 ; 224–254 | DOI | MR | Zbl | MR | Zbl

[124] Solomonoff R. J., “Complexity-based induction systems: comparisons and convergence theorems”, IEEE Transactions on Information Theory, IT-24, 1978, 422–432 | MR | Zbl

[125] Sudborough I. H., Computation by multi-head writing finite automata, Ph. D. Thesis, Pennsylvania State University, University Park, 1974

[126] Sudborough I. H., “One-way multihead writing finite automata”, Information and Control, 30 (1976), 1–20 ; FOCS, 1971 | DOI | MR | Zbl

[127] Thompson C. D., “Area-Time complexity for VLSI”, 11th STOC, 1979 | MR

[128] Turing A. M., “On computable numbers with an application to the Entscheidungsproblem”, Proc. London Math. Soc., 42 (1936), 230–265 ; Correction, Ibid, 43 (1937), 544–546 | DOI | DOI

[129] Valiant L., G. Brebner, “Universal Schemes for parallel communication”, 13th STOC, 1981

[130] Valiant L., “A Theory of the Learnable”, Comm. ACM, 27 (1984), 1134–1142 | DOI | Zbl

[131] Valiant L., “Deductive Learning”, Phil. Trans. Royal Soc. Lond., A 312 (1984), 441–446 | DOI | MR | Zbl

[132] Vazirani U., V. Vazirani, “A ratural encoding scheme proved probabilistic polynomial complete”, Proc. 23rd IEEE Symp. on Foundations of Computer Science, 1982 | MR

[133] Ville J., Etude critique de la concept de Collectif, Gauthier-Villars, Paris, 1939

[134] Vitanyi P. M. B., L. Meertens, “Big Omega versus the wild functions”, SIGACT News, 16:4 (1985), 56–59 | DOI

[135] Vitányi P. M. B., “On the simulation of many storage heads by one”, Theoretical Computer Science, 34 (1984), 157–168 ; ICALP, 1982 | DOI | MR | Zbl

[136] Vitányi P. M. B., “On two-tape real-time cemputation and queues”, Journal of Computer and System Sciences, 29 (1984), 303–311 | DOI | MR | Zbl

[137] Vitányi P. M. B., “Square time is optimal for the simulation of a pushdown store by an oblivious one-head tape unit”, Information Processing Letters, 21 (1985), 87–91 | DOI | MR | Zbl

[138] Vitányi P. M. B., “An $N^{**}1.618$ lower bound on the time to simulate one queue or two pushdown stores by one tape”, Information Processing Letters, 21 (1985), 147–152 | DOI | MR | Zbl

[139] Wald A., “Sur la notion de collectif dans la calcul ther probabilites”, Comptes Rendus des Sceánces de l'Académie des Sciences, 202 (1936), 1080–1083

[140] Watanabe O., “Comparison of polynomial time completeness notions”, Theoretical Computer Science, 53 (1987)

[141] Yao A. C.-C., R. L. Rivest, “$k+1$ heads are better than $k$”, JACM, 25 (1978), 337–340 ; Proc. 17th FOCS, 1976, 67–70 | DOI | MR | Zbl

[142] Zvonkin A. K., L. A. Levin, “The complexity of finite objects and the development of the concepts of information and randomness by means of the Theory of Algorithms”, Russ. Math. Surv., 25 (1970), 83–124 | DOI | MR | Zbl

[143] Barzdin Ya. M., “Slozhnost raspoznavaniya simmetrii na mashinakh Tyuringa”, Problemy kibernetiki, no. 15, Nauka, M., 1965, 245–248 | MR

[144] Kolmogorov A. N., “K logicheskim osnovaniyam teorii informatsii i teorii veroyatnostei”, Problemy peredachi informatsii, 5:3 (1969), 3–7 | MR | Zbl

[145] Vyugin V. V., “Algoritmicheskaya entropiya (slozhnost) konechnykh ob'ektov i ee primenenie k opredeleniyu sluchainosti i kolichestva informatsii”, Semiotika i informatika, no. 16, VINITI, M., 1981, 14–43 | MR

[146] Uspenskii V. A., Semenov A. L., Teoriya algoritmov: osnovnye otkrytiya i prilozheniya, Nauka, M., 1987, 288 pp. | MR

[147] Hennie F. C., Stearns R. E., “Two tape simulation of multitape Turing machines”, J. Assoc. Comput. Machinery, 13:4 (1966), 533–546 ; Khenni F. K., Stirnz R. E., “Modelirovanie mnogolentochnoi mashiny Tyuringa na dvukhlentochnoi”, Problemy matematicheskoi logiki, Mir, M., 1970, 194–212 | MR | Zbl

[148] Hennie F. C., “One tape off-line Turing machine computations”, Information and Control, 8:6 (1965), 553–578 ; Khenni F. K., “Vychisleniya na odnolentochnoi mashine Tyuringa s zapisyu na lente”, Problemy matematicheskoi logiki, Mir, M., 223–248 | DOI | MR

[1] Agafonov B. N., On algorithms, frequency and randomness, Ph. D. Thesis, Novosibirsk, 1970

[2] Alekseev V. M., M. V. Yakobson, “Symbolic dynamics and hyperbolic dynamical systems”, Physics Reports, 75 (1981), 287–325 | DOI | MR

[3] Allender E., “Some consequences of the existence of pseudorandom generators”, Proc. 19th ACM Symposium on Theory of Computing, 1987, 151–159

[4] Balcazar J., R. Book, “On generalized Kolmogorov complexity”, Proc. 1st Structure in Complexity Theory Conf., Springer LNCS, 223, 1986, 334–340 | MR

[5] Barzdin' Y. M., “On computability by probabilistic machines”, Soviet Math. Dokl., 10 (1969), 1464–1467 | Zbl

[6] Barzdin' Y. M., “On the relative frequency of solution of algorithmically unsolvable mass problems”, Soviet Math. Dokl., 11 (1970), 459–462 | Zbl

[7] Barzdin' Y. M., R. V. Freivald, “On the prediction of general recursive functions”, Soviet Math. Dokl., 13 (1972), 1251–1254

[8] Barzdin' Y. M., “Algorithmic information theory”, Encyclopaedia of Mathematics, Vol. 1, D. Reidel (Kluwer Academic Publishers), Dordrecht, 1988, 140–142; Updated and annotated, Soviet Mathematical Encyclopaedia

[9] Bennett C. H., G. Grindstein, “Role of irreversibility in stabilizing complex and nonergodic behavior in locally interacting discrete systems”, Physical Review Letters, 55 (1985), 657–660 | DOI

[10] Bennett C. H., “On the nature and origin of complexity in discrete, homogeneous, locallyinteracting systems”, Foundations of Physics, 1986 (to appear)

[11] Blum L., M. Blum, “Toward a mathematical theory of inductive inference”, Information and Control, 28 (1975), 125–155 | DOI | MR | Zbl

[12] Blum M., “On the size of machines”, Information and Control, 11 (1967), 257–265 | DOI | MR | Zbl

[13] Blum M., S. Micali, “How to generate cryptographically strong sequences of pseudo random bits”, SIAM J. on Computing, 13 (1984), 850–864 | DOI | MR | Zbl

[14] Brudno A. A., “Entropy and the complexity of trajectories of a dynamical system”, Trans. Mosc. Math. Soc., 44 (1983), 127–151 | MR

[15] Calude C., Theories of Computational Complexity, Chapter 4, North-Holland, Amsterdam, 1988 | MR | Zbl

[16] Chaitin G. J., “On the length of programs for computing finite binary sequences: statistical considerations”, J. Assoc. Comp. Mach., 16 (1969), 145–159 | MR | Zbl

[17] Chaitin G. J., “On the simplicity and speed of programs for computing infinite sets of natural numbers”, J. Assoc. Comp. Mach., 16 (1969), 407–422 | MR | Zbl

[18] Chaitin G. J., “On the difficulty of computations”, IEEE Transactions on Information Theory, IT-16 (1970), 5–9 | DOI

[19] Chaitin G. J., “Information-theoretic computations complexity”, IEEE Transactions on Information Theory, IT-20 (1974), 10–15 | DOI | MR

[20] Chaitin G. J., “Algorithmic entropy of sets”, Computers and Mathem. with Applications, 2 (1976), 233–245 | DOI | MR | Zbl

[21] Chaitin G. J., J. T. Schwartz, “A note on Monte-Carlo primality tests and Algorithmic Information Theory”, Communications in Pure and Applied Mathematics, 31 (1978), 521–527 | DOI | MR | Zbl

[22] Chaitin G. J., “Toward a mathematical definition of “life””, The Maximal Entropy Formalism, ed. M. Tribus, MIT Press, Cambridge, Mass., 1979, 477–498 | MR

[23] Chaitin G. J., Collected Papers on Algorithmic Information Theory, Aug. 1986, IBM T. J. Watson Research Center | Zbl

[24] Chaitin G. J., Algorithmic Information Theory, Cambridge University Press, 1987 | MR | Zbl

[25] Cheong S., T. M. Cover, “Some equivalences between Shannon entropy and Kolmogorov complexity”, IEEE Trans. on Information Theory, May 1978, IT-24.3 | MR

[26] Chung F. R. K., R. E. Tarjan, W. J. Paul, R. Reischuk, Coding strings by pairs of strings, Research Report, IBM Research Laboratory, San Jose, 1985, Undated and no registration number | MR

[27] Cover T. M., Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin, Statistics Dept. Rept. 12, October 1974, Stanford University

[28] Daley R. P., “Minimal-program complexity of sequences with restricted resources”, Information and Control, 23 (1973), 301–312 | DOI | MR | Zbl

[29] Daley R. P., “An example of an information and computational resource trade-off”, J. ACM, 20 (1973), 687–695 | DOI | MR | Zbl

[30] Daley R. P., “Noncomplex sequences: characterizations and examples”, J. for Symbolic Logic, 41 (1976), 626–638 | DOI | MR | Zbl

[31] Daley R. P., “Quantitative and qualitative information in computation”, Information and Control, 45 (1980), 236–244 | DOI | MR | Zbl

[32] Dies J. E., “Information et complexite”, Ann. Inst. Henri Poincare, B, 12 (1976), 365–390 ; ibidem, 14 (1978), 113–118 | MR | Zbl | MR | Zbl

[33] Dietzfelbinger M., W. Maass, “The complexity of matrix transposition on one-tape off-line Turing machines with output tape”, International Conference on Automata, Languages and Programming, Springer LNCS, 1988 | MR

[34] Duris P., Z. Galil, W. Paul, R. Reischuk, “Two nonlinear lower bounds for on-line computations”, Information and Control, 60 (1984), 1–11 | DOI | MR | Zbl

[35] Ford J., “How random is a coin toss?”, Physics Today, April 1983 | MR

[36] Gardner M., “The random number omega bids fair to hold the mysteries of the universe”, May 1979, Scientific American, 241, 20–34

[37] Goldreich O., S. Goldwasser, S. Micali, “How to construct random functions”, Journal ACM, 1986, 792–807 | DOI | MR

[38] Gacs P., J. Korner, “Common information is far less than mutual information”, Problems of Control and Information Theory, 2 (1973), 149–162 | MR | Zbl

[39] Gacs P., Komplexitat and Zufalligkeit, Ph. D. Thesis, Fachbereich Mathematik, J. W. Goethe Universitat, Frankfurt am Mein, 1978 | Zbl

[40] Gacs P., “Exact expressions for some randomness tests”, Z. Math. Logik Grundl. Math., 26 (1980), 385–394 | DOI | MR | Zbl

[41] Gacs P., “On the relation between descriptional complexity and algorithmic complexity”, Theoretical Computer Science, 22 (1983), 71–93 | DOI | MR | Zbl

[42] Gacs P., “Every sequence is Turing-reducible to a random sequence”, Information and Control, 70 (1986), 186–192 | DOI | MR | Zbl

[43] Gacs P., Lecture notes on descriptional complexity and randomness, Manuscript, October 1987, Boston University, Cambridge, Mass.

[44] Kamae T., “On Kolmogorov's complexity and information”, Osaka J. Math., 10 (1973), 305–307 | MR | Zbl

[45] Kanovich M. I., “On the decision complexity of algorithms”, Soviet Math. Dokl., 10 (1969), 700–701

[46] Kanovich M. I., N. V. Petri, “Some theorems on the complexity of normal algorithms and their computations”, Soviet Math. Dokl., 10 (1969), 233–234

[47] Kanovich M. I., “On the complexity of enumeration and decision of predicates”, Soviet Math. Dokl., 11 (1970), 17–20

[48] Katseff H. P., “Complexity dips in infinite binary sequences”, Information and Control, 38 (1978), 258–263 | DOI | MR | Zbl

[49] Katseff H. P., M. Sipser, “Several results in program size complexity”, Theoretical Computer Science, 1981, 291–309 ; Proc. 18th IEEE FOCS, 1977, 82 | DOI | MR | Zbl | MR

[50] Ko Ker-I, “On the definition of infinite pseudo-random sequences”, Theoretic. Compute Sci., 48 (1986), 9–34 | DOI | MR

[51] Ko Ker-I, P. Orponen, U. Schoning, O. Watanabe, “What is a hard instance of a computational problem”, Structure in Complexity Theory, Springer LNCS, 1986, 197–217 | MR | Zbl

[52] Kolmogorov A. N., “Some theorems on algorithmic entropy and the algorithmic quantity of information”, Uspekhi Mat. Nauk, 23:2 (1968), 201

[53] Lambalgen M. van, Algorithmic Information Theory, Manuscript, Dept. Mathematics and Computer Science, Delft University of Technology, Delft, 1988 | MR

[54] Laplace P. S., A Philosophical Essay on Probabilities, Dover, New York, 1819, 16–17 | MR

[55] Levin L. A., Some theorems on the algorithmic approach to probability theory abd information theory, Ph. D. Thesis, Moscow University, 1971 | Zbl

[56] Levin L. A., “On the notion of a random sequence”, Soviet Math. Dokl., 14 (1973), 1413–1416 | Zbl

[57] Levin L. A., “On storage capacity for algorithms”, Soviet Math. Dokl., 14 (1973), 1464–1466 | Zbl

[58] Levin L. A., “On the principle of conservation of information in intuitionistic mathematics”, Soviet Math. Dokl., 17 (1976), 601–605 | MR | Zbl

[59] Levin L. A., “Uniform tests of randomness”, Soviet Math. Dokl., 17 (1976), 337 | MR | Zbl

[60] Levin L. A., “Various measures of complexity for finite objects (axiomatic description)”, Soviet Math. Dokl., 17 (1976), 522–526 | MR | Zbl

[61] Levin L. A., V. V. V'jugin, “Invariant properties of information bulks”, Springer Lecture Notes in Computer Science, 53, Springer Verlag, Berlin, 1977, 359–3364 | MR

[62] Levin L. A., “One-way functions and pseudorandom generators”, Proc. 17th ACM Symposium on Theory of Computing, 1985, 363–365

[63] Li M., “Lower bounds on string-matching”, 1984 (to appear)

[64] Li M., On one tape versus two stacks, Report TR-84-636, Jan. 1984, Computer Science Department, Cornell University

[65] Loveland D. W., Trans. Amer. Math. Soc., 125 (1966), 497–510 | DOI | MR | Zbl

[66] Loveland D. W., “On minimal-program complexity measures”, Proceedings ACM Symposium on Theory of Computing, 1969

[67] Loveland D. W., “A variant of the Kolmogorov concept of complexity”, Information and Control, 15 (1969), 510–526 | DOI | MR | Zbl

[68] Maass W., “Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines”, Proceedings 16th ACM Symposium on Theory of Computing, 1984, 401–408

[69] Maass W., “Are recursion theoretic arguments useful in complexity theory?”, Logic, Methodology and Philosophy of Science, VII, eds. Barcan Marcus et. al., North-Holland, Amsterdam, 1986, 141–158 | MR

[70] Manin Y. I., “Kolmogorov complexity”, A Course in Mathematical Logic, Springer Verlag, 1977, 225–230

[71] Manin Y. I., “Expanding constructive universes”, Algorithms in Modern Mathematics and Computer Science, Lecture Notes in Computer Science, 122, eds. Ershov A. P., D. E. Knuth, Springer Verlag, Berlin, 1981, 255–260 | MR

[72] Marandzhyan G. B., “On certain properties of asymptotically optimal recursive function”, Izv. Akad. Nauk Armyan. SSSR, 4 (1966), 3–22

[73] Markov A. A., “On normal algorithms which compute Boolean functions”, Soviet Math. Dokl., 5 (1964), 922–924 | MR | Zbl

[74] Markov A. A., “On normal algorithms associated with the computation of Boolean functions and predicates”, Izv. Akad. Nauk SSSR Ser. Mat., 31 (1967), 161–208 | MR | Zbl

[75] Martin-Lof P., “On the concept of a random sequence”, Theory Probability Appl., 11 (1966), 177–179 | DOI

[76] Martin-Lof P., “Algorithmen und zufallige Folgen”, Lecture Notes, University of Erlangen, 1966

[77] Martin-Lof P., “The literature of von Mises' Kollektivs revisited”, Theoria, 35:1 (1969), 12 | MR

[78] Martin-Lof P., “Algorithms and randomenss”, Rev. of International Statist. Inst., 37 (1969), 265–272 | DOI

[79] Martin-Lof P., “Complexity oscilations in infinite binary sequences”, Zeitschrift fur Wahrschleinlichkeitstheory und Verwandte Gebiete, 19 (1971), 225–230 | DOI | MR

[80] Miller V. S., “Data Compression Algorithms”, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1986, 107–118 | MR

[81] Nikol'skii S. M., “Aleksandrov and Kolmogorov in Dnepropetrovsk”, Russian Math. Surveys, 38 (1983), 41–55 | DOI | MR

[82] Paturi R., Study of certain probabilistic models of information transfer and on-line computation, Ph. D. Thesis, Penn State University, 1985

[83] Peterson G., “Succinct representations, random strings and complexity classes”, Proc. 21st IEEE Symposium on Foundations of Computer Science, 1980, 86–95

[84] Petri N. V., “The complexity of algorithms and their operating time”, Soviet Math. Dokl., 10 (1969), 547–549 | MR | Zbl

[85] Petri N. V., “Algorithms connected with predicates and Boolean functions”, Soviet Math. Dokl., 10 (1969), 294–297 | Zbl

[86] Rissanen J., “Stochastic complexity and modelling”, Annals of Statistics, 14 (1986), 1080–1100 | DOI | MR | Zbl

[87] Schnorr C. P., “Process complexity and effective random tests”, J. Comput. System Sciences, 7 (1973), 376 | DOI | MR | Zbl

[88] Schnorr C. P., Rekursive Funktionen und ihre Komplexitat, Teubner, Stuttgart, 1974 | MR | Zbl

[89] Schnorr C. P., G. Stumpe, “A characterization of complexity sequences”, Z. Math. Logik und Grundlag. Math., 21 (1975), 47–56 | MR | Zbl

[90] Schnorr C. P., “A review of the theory of random sequences”, Proc. 5th Int. Congr. on Logic, Math. and Phil. of Sci. (August 1975), London, Ontario

[91] Schnorr C. P., “A survey of the theory of random sequences”, Basic Problems in Methodology and linquistics, eds. Butts R. E., J. Hintikka, D. Reidel, Dordrecht, 1977, 193–210 | MR

[92] Schnorr C. P., P. Fuchs, “General random sequences and learnable sequences”, J. Symbolic Logic, 42 (1977), 329–340 | DOI | MR

[93] Shannon C. E., “The mathematical theory of communication”, Bell System Tech. J., 27 (1948), 379–423 ; 623–656 | MR

[94] Solomonoff R. J., “Training sequences for mechanized induction”, Self organizing Systems, ed. M. Yovits, 1962

[95] Solomonoff R. J., “Inductive inference theory - a unified approach to problems in Pattern Recognition and Artificial Intelligence”, 4th International Conference on Artificial Intelligence (Georgia, USSR), Tbilisi, 1975, 274–280

[96] Solomonoff R. J., Complexity based induction systems: comparisons and convergence theorems, Tech. Rep. RR-329, August, 1976, Rockford Research, Cambridge, Mass.

[97] Solomonoff R. J., “Perfect training sequences and the costs of corruption - A progress report on Inductive Inference research”, Memorandum, Oxbridge Research, P.O. box 559, August 1982, Cambridge, Mass. 02238

[98] Solomonoff R. J., “Optimum sequential search”, Memorandum, Oxbridge Research, P.O. box 669, June 1984, Cambridge, Mass. 02238

[99] Solomonoff R. J., “An application in Algorithmic Probability to problems of Artificial Intelligence”, Uncertainty in Artificial Intelligence, ed. J. F. Lemmer, North-Holland, 1986, 473–491

[100] Solovay R., “On random r.e. sets”, Non-Classical Logic, Model Th. and Computability, North-Holland, 1977, 283–307 | MR

[101] Staiger L., Complexity and Entropy, Lecture Notes in Computer Science, 118, Springer Verlag, 1981 | MR

[102] Trankhtenbrot B. A., “A survey of Russian approaches to perebor (brute-forcesearch) algorithms”, Annals of the History of Computing, 6 (1984), 384–400 | DOI | MR

[103] Uspenski V. A., A. L. Semenov, “What are the gains of the theory of algorithms; basic developments connected with the concept of algorithm and with its application in mathematics”, Algorithms in Modern Mathematics and Computer Science, Lecture Notes in Computer Science, 122, eds. Ershov A. P., D. E. Knuth, Springer Verlag, Berlin, 1981, 100–234 | MR

[104] Vitányi P. M. B., One queue or two pushdown stores take square time on a one-head tape unit, Computer Science Technical Report CS-R8406, March 1984, CWI, Amsterdam

[105] Wald A., “Die Wiederspruchsfreiheit des Kollektivbegriffes der Wahrscheinlichkeitsrechnung”, Ergebnisse eines mathematischen Kolloquiums, 8 (1937), 38–72

[106] Watanabe O., “Comparison of polynomial time completeness notions”, Theoretical Computer Science, 53 (1987)

[107] Willis D. G., “Computational complexity and probability constructions”, J. ACM, 17 (1970), 241–259 | DOI | MR | Zbl

[108] Yao A., “Theory and application of trapdoor functions”, Proceedings 23rd IEEE Symposium on Foundations of Computer Science, 1982, 80–91 | MR

[109] Asarin E. A., “O nekotorykh svoistvakh sluchainykh v algoritmicheskom smysle konechnykh ob'ektov”, DAN, 295:4 (1987), 782–785 | MR | Zbl

[110] Asarin E. A., “O nekotorykh svoistvakh $\Delta$-sluchainykh po Kolmogorovu konechnykh posledovatelnostei”, Teoriya veroyatnostei i ee primeneniya, 32:3 (1987), 556–558 | MR | Zbl

[111] Asarin E. A., Pokrovskii A. V., “Primenenie kolmogorovskoi slozhnosti k analizu dinamiki upravlyaemykh sistem”, Avtomatika i telemekh., 1986, no. 1, 25–33 | MR | Zbl

[112] Asarin E. A., “Individual random continious functions”, Tez. dokl. Pervogo Vsemirnogo Kongressa Obsch-va matem. statist. i teorii veroyatnostei im. Bernulli, T. I, ed. Prokhorov Yu. V., Nauka, M., 1986, 450

[113] Vovk V. G., “Zakon povtornogo logarifma dlya sluchainykh po Kolmogorovu, ili khaoticheskikh, posledovatelnostei”, Teoriya veroyatnostei i ee primeneniya, 32:3 (1987), 456–468 | MR | Zbl

[114] Vovk V. G., “Algoritmicheskaya teoriya informatsii i zadacha prognozirovaniya”, Slozhnostnye problemy matematicheskoi logiki, eds. Kanovich M. I. i dr., Kalininskii gos. un-t, Kalinin, 1985, 21–24 | MR

[115] Vovk V. G., “On use of algorithmic notions of randomness and simplicity in the mathematical statistics”, Tez. dokl. Pervogo Vsemirnogo Kongressa Obsch-va matem. statist. i teorii veroyatnostei im. Bernulli, Nauka, M., 1986, 456

[116] Vyugin V. V., “O defekte sluchainosti konechnogo ob'ekta otnositelno mer s zadannymi granitsami ikh slozhnosti”, Teoriya veroyatnostei i ee primeneniya, 32:3 (1987), 558–563 | MR

[117] V'jugin V. V., “Some estimates for nonstochastic sequences”, Tez. Dokl. Pervogo Vsemirnogo Kongressa Obsch-va Matem. statist. i teorii veroyatnostei im. Bernulli, Nauka, M., 1986, 455 | MR

[118] A. N. Kolmogorov, V. A. Uspensky, “Algorithms and randomness”, Probability Theory and Applications, Proc. 1st World Congress of the Bernoulli Society (Tashkent, USSR, 8–14 Sept. 1986), eds. Yu. A. Prohorov, V. V. Sazonov, VNU Science Press, Utrecht, 1987, 3–53 | MR

[119] Muchnik An. A., “On the extraction of common information of two words”, Tez. dokl. Pervogo Vsemirnogo Kongressa Obsch-va matem. statist. i teorii veroyatnostei im. Bernulli, Nauka, M., 1986, 453

[120] Muchnik An. A., “Nizhnie predely chastot v vychislimykh posledovatelnostyakh i relyativizovannaya apriornaya veroyatnost”, Teoriya veroyatnostei i ee primeneniya, 32:3 (1987), 563–565 | MR | Zbl

[121] Kolmogorov A. N., Uspenskii V. A., “Algoritmy i sluchainost”, Teoriya veroyatnostei i ee primeneniya, 32:3 (1987), 425–455 | MR | Zbl

[122] Shen A. Kh., “Aksiomaticheskoe opisanie ponyatiya entropii konechnogo ob'ekta”, Tez. VIII Vses. konf. po logike i metodologii nauki, Izd-vo LatvGU, Vilnyus, 1982, 104–105

[123] Shen A. Kh., “Ischislenie zadach i $F_0$-prostranstva”, Tez. dokl. VI Vses. konf. matem. logiki, Tbilisi, 1982, 204 | Zbl

[124] Shen A. Kh., “Ponyatie $\alpha,\beta$-stokhastichnosti po Kolmogorovu i ego svoistva”, DAN, 271:6 (1983), 1337–1340 | MR | Zbl

[125] Shen A. Kh., “K logicheskim osnovam primeneniya teorii veroyatnostei”, Semioticheskie aspekty formalizatsii intellektualnoi deyatelnosti, Sb., VINITI, M., 1983, 144–146

[126] Shen A. Kh., “Algoritmicheskie varianty ponyatiya entropii”, DAN, 276:3 (1984), 563–566 | MR | Zbl

[127] Shen A. Kh., “Chastotnyi podkhod k opredeleniyu ponyatiya sluchainoi posledovatelnosti”, Semiotika i informatika, no. 18, VINITI, M., 1982, 14–42

[128] Sen A., “One more definition of random sequence with respect to computable mesure”, Tez. dokl. Pervogo Vsemirnogo Kongressa Obsch-va matem. statist. i teorii veroyatnostei im. Bernulli, Nauka, M., 1986, 454