Enumerations including laconic enumerators

DOI10.1016/J.TCS.2017.08.001zbMATH Open1383.68040OpenAlexW2747848014MaRDI QIDQ2410366FDOQ2410366

Sanjay Jain, Jason Teutsch

Publication date: 17 October 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.08.001

Recommendations

• scientific article; zbMATH DE number 1028226
• scientific article; zbMATH DE number 4006240
• Regular enumerations
• Enumeration by e
• A Course in Enumeration
• Numeration and enumeration
• Exact enumerations
• Exact enumerations
• An Introduction to Enumeration

zbMATH Keywords

Kolmogorov complexityrecursion theoryKolmogorov numberingslist approximationsminimal programs

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Cites Work

• Algorithmic Randomness and Complexity
• Short lists with short programs in short time
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Three approaches to the quantitative definition of information^*
• An introduction to Kolmogorov complexity and its applications
• Information-theoretic characterizations of recursive infinite strings
• Short lists for shortest descriptions in short time
• Short Lists with Short Programs in Short Time – A Short Proof
• Enumerations of the Kolmogorov function
• A proof of Beigel's cardinality conjecture
• Frequency computations and the cardinality theorem
• Index sets and universal numberings
• Optimal enumerations and optimal gödel numberings
• On approximate decidability of minimal programs
• Short lists with short programs from programs of functions and strings
• The complexity of the set of nonrandom numbers

Cited In (4)

• On approximate decidability of minimal programs
• Enumerations of the Kolmogorov function
• Searching for shortest and least programs
• Enumeration (18th–20th centuries)

This page was built for publication: Enumerations including laconic enumerators

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