In this paper we introduce a new feasible notion of Bennett's logical depth based on pebble transducers. This notion is defined based on the difference between the minimal length descriptional complexity of prefixes of infinite sequences from the perspective of finite-state transducers and pebble transducers. Our notion of pebble-depth satisfies the four fundamental properties of depth: i.e. deep sequences exist, trivial sequences are not deep, random sequences are not deep, and the existence of a slow growth law type result. We also compare pebble-depth to other depth notions based on finite-state transducers, pushdown compressors, and the Lempel-Ziv 78 compression algorithm. We first demonstrate how there exists a normal pebble-deep sequence even though there is no normal finite-state-deep sequence. We next build a sequence that has a pebble-depth level of roughly 1, a pushdown-depth level of roughly 1/2 and a finite-state-depth level of roughly 0. We then build a sequence that has a pebble-depth level of roughly 1/2 and a Lempel-Ziv-depth level of roughly 0.

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.

This paper examines Automatic Complexity, a complexity notion introduced by Shallit and Wang in 2001. We demonstrate that there exists a normal sequence $T$ such that $I(T) = 0$ and $S(T) \leq 1/2$, where $I(T)$ and $S(T)$ are the lower and upper automatic complexity rates of $T$ respectively. We furthermore show that there exists a Champernowne sequence $C$, i.e. a sequence formed by concatenating all strings of length $1$ followed by concatenating all strings of length $2$ and so on, such that $S(C) \leq 2/3$.