Feasible Depth
From MaRDI portal
Publication:5425324
DOI10.1007/978-3-540-73001-9_24zbMath1151.68433arXivcs/0701123MaRDI QIDQ5425324
Publication date: 13 November 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0701123
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03D80: Applications of computability and recursion theory
Related Items
Pushdown and Lempel-Ziv depth, Finite state incompressible infinite sequences, Finite state complexity, A normal sequence compressed by PPM* but not by Lempel-Ziv 78, Lowness and logical depth, Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report), Polylog depth, highness and lowness for E, Depth, Highness and DNR Degrees, On the Polynomial Depth of Various Sets of Random Strings, On the Difference Between Finite-State and Pushdown Depth