Kolmogorov Complexity and Symmetric Relational Structures

&
Journal of Symbolic Logic 63 (3):1083-1094 (1998)
  Copy   BIBTEX

Abstract

We study partitions of Fraisse 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.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,897

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Kolmogorov complexity and symmetric relational structures.W. L. Fouché & P. H. Potgieter - 1998 - Journal of Symbolic Logic 63 (3):1083-1094.
Recursive events in random sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
Kolmogorov complexity for possibly infinite computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Symmetric generalized galois logics.Katalin Bimbó & J. Michael Dunn - 2009 - Logica Universalis 3 (1):125-152.
Kolmogorov Complexity and Noncomputability.George Davie - 2002 - Mathematical Logic Quarterly 48 (4):574-581.
Complexity as a Framework for Prediction, Optimization, and Assurance.S. F. Bush - 2004 - In Susan Shannon (ed.), Focus on Computer Science Research. New York: Nova Science.
Kolmogorov complexity and set theoretical representations of integers.Marie Ferbus-Zanda & Serge Grigorieff - 2006 - Mathematical Logic Quarterly 52 (4):375-403.
A Pigeonhole Property for Relational Structures.Anthony Bonato & Dejan Delić - 1999 - Mathematical Logic Quarterly 45 (3):409-413.
On complexity of Ehrenfeucht–Fraïssé games.Bakhadyr Khoussainov & Jiamou Liu - 2010 - Annals of Pure and Applied Logic 161 (3):404-415.
The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.
Every 2-random real is Kolmogorov random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
Relative Kolmogorov complexity and geometry.Stephen Binns - 2011 - Journal of Symbolic Logic 76 (4):1211-1239.
Elementary differences between the degrees of unsolvability and degrees of compressibility.George Barmpalias - 2010 - Annals of Pure and Applied Logic 161 (7):923-934.
Kolmogorov complexity estimates for detection of viruses in biologically inspired security systems: A comparison with traditional approaches.Sanjay Goel & Stephen F. Bush - 2003 - Complexity 9 (2):54-73.
Program Size Complexity for Possibly Infinite Computations.Verónica Becher, Santiago Figueira, André Nies & Silvana Picchi - 2005 - Notre Dame Journal of Formal Logic 46 (1):51-64.

Analytics

Added to PP
2017-02-21

Downloads
2 (#1,804,618)

6 months
1 (#1,471,540)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Willem Fouché
University of South Africa

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references