×

zbMATH — the first resource for mathematics

Process complexity and effective random tests. (English) Zbl 0273.68036

MSC:
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Loveland, D.W., A variant of the Kolmogorov concept of complexity, Inform. control, 15, 510-526, (1969) · Zbl 0188.52101
[2] Kolmogorov, A.N., Tri podhoda k opredeleniju ponjatija “kolicestwo informacii”, Probl. peredaci inform., 1, 3-11, (1965)
[3] Martin-Löf, P., The definition of random sequences, Inform. control, 6, 602-619, (1966) · Zbl 0244.62008
[4] Martin-Löf, P., Complexity oscillations in infinite binary sequences, Z. wahrscheinlich. verw. geb., 19, 225-230, (1971) · Zbl 0212.23103
[5] Schnorr, C.P., Zufälligkeit und wahrscheinlichkeit, () · Zbl 0214.01804
[6] \scC. P. Schnorr, Optimal Enumerations and optimal Gödel numberings. Technical report. University Frankfurt. · Zbl 0316.02044
[7] Solomonoff, R.J., A formal theory of inductive inference, part I, Inform. control, 7, 1-22, (1964) · Zbl 0258.68045
[8] Levin, L.; Zvonkin, A., Die komplexität endlicher objekte und die begründung der begriffe der information und der zufälligkeit mit hilfe der theorie der algorithmen (russisch), Uspekhi matematicheskikh nauk, 156, (1970)
[9] Huffmann, D.A., A method of constructing minimum redundancy codes, Proc. IRE, 40, 10, (1952)
[10] Ville, J., Étude critique de la notion de collectif, () · JFM 65.0547.05
[11] Church, A., On the concept of random sequences, Bull. amer. math. soc., 46, 130-135, (1940) · JFM 66.0601.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.