A note on the Kolmogorov data complexity and nonuniform logical definitions

DOI10.1016/S0020-0190(97)00172-5zbMATH Open1338.03053OpenAlexW2040072426MaRDI QIDQ290271FDOQ290271

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

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

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)

Cites Work

• Title not available (Why is that?)
• Probabilities on finite models
• Title not available (Why is that?)
• An optimal lower bound on the number of variables for graph identification
• The Kolmogorov expression complexity of logics
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• 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)