Back to Search
Start Over
Pushdown and Lempel-Ziv depth.
- Source :
-
Information & Computation . Jun2023, Vol. 292, pN.PAG-N.PAG. 1p. - Publication Year :
- 2023
-
Abstract
- 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]
- Subjects :
- *KOLMOGOROV complexity
*COMPRESSORS
*INFORMATION theory
*TRANSDUCERS
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 292
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 163746635
- Full Text :
- https://doi.org/10.1016/j.ic.2023.105025