The Kolmogorov expression complexity of logics

DOI10.1006/INCO.1997.2636zbMATH Open0879.68055OpenAlexW2055834130MaRDI QIDQ1363784FDOQ1363784

Authors: Jerzy Tyszkiewicz 

Publication date: 11 August 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2fbaf57dcb58ac4c076c33fcaa5b21c59df35e08

Recommendations

• A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law
• A note on the Kolmogorov data complexity and nonuniform logical definitions
• The Kolmogorov expressive power of Boolean query languages
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic

zbMATH Keywords

Kolmogorov complexityexpression complexityfinite-model theory

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (8)

• Combinatorial expressions and lower bounds
• A note on the Kolmogorov data complexity and nonuniform logical definitions
• Complexity estimates for the relation of coincidence of model-theoretic properties with an application to semantic classes
• Logical operations and Kolmogorov complexity
• LATIN 2004: Theoretical Informatics
• Title not available (Why is that?)
• Kolmogorov complexity and set theoretical representations of integers
• Title not available (Why is that?)

This page was built for publication: The Kolmogorov expression complexity of logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363784)