Pushdown and Lempel-Ziv depth.

In previously published work (Jordon and Moser, 2020), notions of finite-state-depth and pushdown-depth were presented. These were based on finite-state transducers and information lossless pushdown compressors. Unfortunately, a complete separation between the two notions was not established. This paper introduces a new formulation of pushdown-depth based on restricting how fast a pushdown compressor's stack can grow. This allows us to do a full comparison by demonstrating the existence of sequences with high finite-state-depth and low pushdown-depth, and vice-versa. A new notion based on the Lempel-Ziv 78 algorithm is also presented. Its difference from finite-state-depth is shown by a Lempel-Ziv deep sequence that is not finite-state deep, and vice versa. Lempel-Ziv-depth's difference from pushdown-depth is shown by building sequences that have a pushdown-depth of roughly 1/2 but low Lempel-Ziv depth, and by a sequence with high Lempel-Ziv depth but low pushdown-depth. Properties of all three notions are also studied. [ABSTRACT FROM AUTHOR]