On the difference between finite-state and pushdown depth

DOI10.1007/978-3-030-38919-2_16MaRDI QIDQ3297767zbMATH OpenOpenAlexFDO

Authors 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 theoryBennett's logical depthKolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• Feasible Depth
• Pushdown dimension
• Recursive computational depth.
• Computational depth and reducibility
• Computational depth and reducibility

Cites work

• Computational depth: Concept and applications
• Feasible Depth
• Finite state complexity
• Finite state incompressible infinite sequences
• Finite-state dimension
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 3598362 (Why is no real title available?)
• scientific article; zbMATH DE number 3266639 (Why is no real title available?)
• On the polynomial depth of various sets of random strings
• Polylog depth, highness and lowness for E
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable

Cited in

(6)

• Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report)
• Bounded pushdown dimension vs Lempel Ziv information density
• Pushdown and Lempel-Ziv depth
• Pebble-depth
• A normal sequence compressed by PPM* but not by Lempel-Ziv 78
• Pushdown dimension

This page was built for publication: On the difference between finite-state and pushdown depth

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