Feasible Depth

DOI10.1007/978-3-540-73001-9_24zbMath1151.68433arXivcs/0701123OpenAlexW2912177004MaRDI QIDQ5425324

David Doty, Philippe Moser

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

zbMATH Keywords

dimensiondepthrandomnesspolynomial-timefinite-state

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Applications of computability and recursion theory (03D80)

Related Items (10)

A normal sequence compressed by PPM* but not by Lempel-Ziv 78 ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Lowness and logical depth ⋮ Depth, Highness and DNR Degrees ⋮ Pushdown and Lempel-Ziv depth ⋮ On the Difference Between Finite-State and Pushdown Depth ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Finite state complexity ⋮ Polylog depth, highness and lowness for E ⋮ Finite state incompressible infinite sequences

This page was built for publication: Feasible Depth