Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 42 for “"Kolmogorov Complexity"”.

  1. On Cryptography and Kolmogorov Complexity

    … problems related to the notion of time-bounded Kolmogorov Complexity (dating back to the 1960s). These results yield the first natural computational problemscharacterizing the feasibility of central primitives and protocols in Cryptography, as well as the first unstructured computational …

    cornell Repository record for On Cryptography and Kolmogorov Complexity (opens in a new tab)

  2. Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets

    We also study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We call a class S of computably enumerable sets bounded if there is an m-incomplete computably enumerable set A such that every set in S is m-reducible to A. For example, we show …

    uiuc Repository record for Kolmogorov Complexity, Strong Reducibilities, and Computably Enumerable Sets (opens in a new tab)

  3. Style Recognition in Music with Context Free Grammars and Kolmogorov Complexity

    The Kolmogorov Complexity of an object is incomputable. But built in its structure is a way to specify description methods of an object that is computable in some sense. Such a description method then can be exploited to quantify the bits of information needed to generate the object from scratch. …

    waterloo Repository record for Style Recognition in Music with Context Free Grammars and Kolmogorov Complexity (opens in a new tab)

  4. Algorithmic specified complexity.

    … not all improbable events convey information. Kolmogorov complexity captures the idea of information as something easily described. But not all easily described objects are information. The proposed Algorithmic Specified Complexity takes into account both Shannon Information and Kolmogorov …

    baylor Repository record for Algorithmic specified complexity. (opens in a new tab)

  5. An information-theoretic approach to language complexity: variation in naturalistic corpora

    … contributes to the typological-sociolinguistic complexity debate that was triggered by challenges (Kusters 2003; McWhorter 2001) of the assumption that all languages are, on the whole, equally complex (e.g. Hockett 1958). A substantial body of research now suggests that languages and language …

    freiburg-diss Repository record for An information-theoretic approach to language complexity: variation in naturalistic corpora (opens in a new tab)

  6. TESTING THE QUANTUM-CLASSICAL BOUNDARY AND DIMENSIONALITY OF QUANTUM SYSTEMS

    … type inequality based solely on the concept of Kolmogorov complexity and normalized information distance (NID), independent of any statistical considerations usually associated with other Bell's inequalities. We documented in detail our procedures in coming up with an estimate to the Kolmogorov …

    nus Repository record for TESTING THE QUANTUM-CLASSICAL BOUNDARY AND DIMENSIONALITY OF QUANTUM SYSTEMS (opens in a new tab) Download file for TESTING THE QUANTUM-CLASSICAL BOUNDARY AND DIMENSIONALITY OF QUANTUM SYSTEMS (opens in a new tab)

  7. Algorithmic Information Theory Applications in Bright Field Microscopy and Epithelial Pattern Formation

    … Information Theory (AIT), also known as Kolmogorov complexity, to unravel the information complexity of GRNs and the resultant multicellular patterns. To obtain a better understanding of Kolmogorov complexity performance, first we study an application in cell image segmentation. There are …

    utahstate Repository record for Algorithmic Information Theory Applications in Bright Field Microscopy and Epithelial Pattern Formation (opens in a new tab)

  8. An Investigation of Feasible Logical Depth and Complexity Measures via Automata and Compression Algorithms

    … simple process or was it generated randomly? Kolmogorov Complexity is a fundamental tool of Algorithmic Information Theory which measures the complexity of such objects. However, there is one major problem: Kolmogorov Complexity is uncomputable. As such, the complexity of such objects are …

    maynooth Download PDF for An Investigation of Feasible Logical Depth and Complexity Measures via Automata and Compression Algorithms (opens in a new tab)

  9. Kolmogorov extraction and resource-bounded zero-one laws

    … sources. We apply these techniques to "extract" Kolmogorov complexity. More formally: 1. for any [alpha]> 0, given a string x with K(x)> (x)[superscript a], we show how to use O(log (x)) bits of advice to efficiently compute another string y, (y) = (x)[superscript omega (1)], with K(y)> (y) - …

    iastate Repository record for Kolmogorov extraction and resource-bounded zero-one laws (opens in a new tab)

  10. Aesthetic Automata: Synthesis and Simulation of Aesthetic Behaviour in Cellular Automata

    … cellular automata (2D CA). The measure of complexity is a core concept in computational approaches to aesthetics. Shannon's information theory provided an objective measure of complexity, which led to the emergence of various informational theories of aesthetics. However, entropy fails to …

    goldsmiths Repository record for Aesthetic Automata: Synthesis and Simulation of Aesthetic Behaviour in Cellular Automata (opens in a new tab) Download PDF for Aesthetic Automata: Synthesis and Simulation of Aesthetic Behaviour in Cellular Automata (opens in a new tab)

  11. Effective fractal dimension: foundations and applications

    … martingales. Imposing computability and complexity constraints on the gales in this characterization gives the constructive and resource-bounded dimensions. These effective dimensions are useful measures of complexity for theoretical computer science and are closely related to other …

    iastate Repository record for Effective fractal dimension: foundations and applications (opens in a new tab)

  12. Encoding Arguments

    … the incompressibility method from the study of Kolmogorov complexity. We use our technique to produce short original proofs for several results. We also explore extensions of the technique to non-uniform input distributions. Finally, we offer a new manner of encoding which allows for real-valued …

    carleton Repository record for Encoding Arguments (opens in a new tab)

  13. Algorithmic randomness and analysis

    … of projections of Euclidean subsets. Using Kolmogorov complexity, we give a new proof of the celebrated Marstrand projection theorem. We also prove, using similar methods, two new lower bounds on projections. The first shows that Marstrand's theorem holds for more general subsets of R^n. The …

    iastate Repository record for Algorithmic randomness and analysis (opens in a new tab)

  14. Image Information Distance Analysis and Applications

    … the two images being compared. The theory of Kolmogorov complexity provides solid groundwork for a generic information distance metric between any objects that minorizes all metrics in the class. The Normalized Information Distance (NID) metric provides a more useful framework. While …

    waterloo Repository record for Image Information Distance Analysis and Applications (opens in a new tab)

  15. Complexity dynamics of learning systems

    We study complexity and generalization in learning systems. We begin by framing learning as a dynamical non-equilibrium process, and suggest that a more complete understanding of machine learning requires methods beyond statistical description. We point out that machine learning must be considered …

    oxford Repository record for Complexity dynamics of learning systems (opens in a new tab)

  16. EFFECTIVE CONCEPT CLASSES OF PAC AND PACi INCOMPARABLE DEGREES, JOINS AND EMBEDDING OF DEGREES

    … the size of the effective concept class using Kolmogorov complexity. To define the jump operator for PACi degrees the join of effective concept classes is constructed and explores the possibility of embedding known degrees to PACi or PAC degrees. If an embedding exists it will enable proving …

    siu-theses Repository record for EFFECTIVE CONCEPT CLASSES OF PAC AND PACi INCOMPARABLE DEGREES, JOINS AND EMBEDDING OF DEGREES (opens in a new tab)

  17. Non-linear dynamical analysis of biosignals

    … algorithms were developed to calculate the Kolmogorov complexity and Lyapunov exponent, which are nonlinear descriptors and enable the randomness and chaotic nature of ECG signals to be estimated. These measures of randomness and chaotic nature enable us to apply correct interrogative …

    strathclyde Repository record for Non-linear dynamical analysis of biosignals (opens in a new tab)

Page 1 of 3