Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-16T11:18:34.205Z Has data issue: false hasContentIssue false
  • English
  • Français

Kolmogorov complexity and symmetric relational structures

Published online by Cambridge University Press:  12 March 2014

W. L. Fouché  and
P. H. Potgieter
W. L. Fouché
Affiliation:
Department of Mathematics and Applied Mathematics, University of Pretoria, 0002 Pretoria, South Africa E-mail: [email protected]
P. H. Potgieter
Affiliation:
Department of Quantitative Management, University of South Africa, Po Box 392, 0003 Pretoria, South Africa E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study partitions of Fraïssé limits of classes of finite relational structures where the partitions are encoded by infinite binary strings which are random in the sense of Kolmogorov-Chaitin.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 3 , September 1998 , pp. 1083 - 1094
Copyright
Copyright © Association for Symbolic Logic 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Brightwell, G., Prömel, H. J., and Steger, A., The average number of linear extensions of a partial order, Journal of Combinatorial Theory, Series A, vol. 73 (1996), pp. 193–206.CrossRefGoogle Scholar
[2]Chaitin, G. J., Algorithmic information theory, Cambridge University Press, 1987.CrossRefGoogle Scholar
[3]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[4]Compton, K. J., Laws in logic and combinatorics, Algorithms and order (Rival, I., editor), Kluwer Academic Publishers, Dordrecht, 1989, pp. 353–383.CrossRefGoogle Scholar
[5]Fouché, W. L., Identifying randomness given by high descriptive complexity, Acta Applicandae Mathematicae, vol. 34 (1994), pp. 313–328.CrossRefGoogle Scholar
[6]Fouché, W. L., Descriptive complexity and reflective properties of combinatorial configurations, Journal of the London Mathematical Society, Second Series, vol. 54 (1996), pp. 199–208.CrossRefGoogle Scholar
[7]Fraïssé, R., Sur l'extension aux relations de quelques propriétés des ordres, Annates Scientifiques de l'École Normale Superieure, Quatrième Série, vol. 71 (1954), pp. 363–388.CrossRefGoogle Scholar
[8]Gács, P., Randomness and probability—complexity of description, Encyclopedia of statistical sciences, John Wiley & Sons, 1986, pp. 551–555.Google Scholar
[9]Gács, P., A review of G. Chaitin's algorithmic information theory, this Journal, vol. 54 (1989), pp. 624–627.Google Scholar
[10]Hinman, P. G., Recursion-theoretic hierarchies, Springer-Verlag, New York, 1978.CrossRefGoogle Scholar
[11]Hodges, W., Model theory, Cambridge University Press, Cambridge, 1993.CrossRefGoogle Scholar
[12]Jockusch, C. G. Jr., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[13]Kleitman, D. J. and Rothschild, B. L., Asymptotic enumeration of partial orders on a finite set, Transactions of the American Mathematical Society, vol. 205 (1975), pp. 205–220.CrossRefGoogle Scholar
[14]Kolmogorov, A. N., Three approaches to the quantitative definition of information, Probl. Inform. Transmission, vol. 1 (1965), pp. 1–7.Google Scholar
[15]Kolmogorov, A. N. and Uspenskii, V. A., Algorithms and randomness, Theory Probability and its Applications, vol. 32 (1987), pp. 389–412.CrossRefGoogle Scholar
[16]Martin-Löf, P., The definition of random sequences, Information and Control, vol. 9 (1966), pp. 602–619.CrossRefGoogle Scholar
[17]Rado, R., Universal graphs and universal functions, Acta Arithmetica, vol. 9 (1964), pp. 393–407.CrossRefGoogle Scholar
[18]Ramsey, F. P., On a problem of formal logic, Proceedings of the London Mathematical Society, vol. 30 (1930), pp. 264–286.CrossRefGoogle Scholar
[19]Specker, E., Ramsey's theorem does not hold in recursive set theory, Studies in logic and the foundations of mathematics, North-Holland, Amsterdam, 1971.Google Scholar
[20]Vitányi, P. and Li, M., An introduction to Kolmogorov complexity and its applications, Springer-Verlag, 1993.Google Scholar