A note on the Kolmogorov data complexity and nonuniform logical definitions

DOI10.1016/S0020-0190(97)00172-5MaRDI QIDQ290271zbMATH OpenOpenAlexFDO

Authors Jerzy Tyszkiewicz

Publication date 1 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00172-5

zbMATH Keywords

finite model theorycombinatorial problemsKolmogorov complexitydescriptive complexity

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Around Kolmogorov complexity: basic notions and results
• Axiomatizing Kolmogorov complexity
• Towards an axiomatic system for Kolmogorov complexity
• The axiomatic power of Kolmogorov complexity
• scientific article; zbMATH DE number 3974293
• Unified characterizations of lowness properties via Kolmogorov complexity
• A note on Kolmogorov complexity and entropy
• scientific article; zbMATH DE number 4208066
• Nonreducible descriptions for the conditional Kolmogorov complexity
• Kolmogorov characterizations of complexity classes

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• An optimal lower bound on the number of variables for graph identification
• Probabilities on finite models
• The Kolmogorov expression complexity of logics
• The hierarchy theorem for generalized quantifiers

This page was built for publication: A note on the Kolmogorov data complexity and nonuniform logical definitions

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