On the Difference Between Finite-State and Pushdown Depth

DOI10.1007/978-3-030-38919-2_16zbMath1440.68143OpenAlexW2999917873MaRDI QIDQ3297767

Liam Jordon, Philippe Moser

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-38919-2_16

zbMATH Keywords

algorithmic information theoryKolmogorov complexityBennett's logical depth

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (3)

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) ⋮ Pushdown and Lempel-Ziv depth

Cites Work

• Finite state incompressible infinite sequences
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Finite state complexity
• Finite-state dimension
• On the polynomial depth of various sets of random strings
• Polylog depth, highness and lowness for E
• Computational depth: Concept and applications
• Feasible Depth
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Difference Between Finite-State and Pushdown Depth