The Kolmogorov expression complexity of logics

DOI10.1006/INCO.1997.2636MaRDI QIDQ1363784zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

expression complexityfinite-model theoryKolmogorov complexity

Mathematics Subject Classification ID

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

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

Cited in

(12)

• Succinctness as a source of complexity in logical formalisms
• The Kolmogorov expressive power of Boolean query languages
• A note on the Kolmogorov data complexity and nonuniform logical definitions
• Combinatorial expressions and lower bounds
• Complexity estimates for the relation of coincidence of model-theoretic properties with an application to semantic classes
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• scientific article; zbMATH DE number 2101962 (Why is no real title available?)
• scientific article; zbMATH DE number 7139948 (Why is no real title available?)
• Kolmogorov complexity and set theoretical representations of integers
• LATIN 2004: Theoretical Informatics
• Logical operations and Kolmogorov complexity
• A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

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)