Algorithmic information theory and computational complexity

DOI10.1007/978-3-642-44958-1_11MaRDI QIDQ2868411zbMATH OpenOpenAlexFDO

Authors Rūsiņš Freivalds

Publication date 17 December 2013

Published in Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-44958-1_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• Finite state complexity
• Finite-state complexity and the size of transducers
• State-size hierarchy for finite-state complexity
• Invariance and Universality of Complexity
• scientific article; zbMATH DE number 3557669

Cited in

(6)

• Some issues in the theory of optimal algorithms and informational complexity
• scientific article; zbMATH DE number 5081004 (Why is no real title available?)
• scientific article; zbMATH DE number 53549 (Why is no real title available?)
• scientific article; zbMATH DE number 1418484 (Why is no real title available?)
• Theory and Applications of Models of Computation
• Algorithmic information theory and undecidability

This page was built for publication: Algorithmic information theory and computational complexity

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