论文标题
下降和Lempel-Ziv深度
Pushdown and Lempel-Ziv Depth
论文作者
论文摘要
本文扩展了现有的，并引入了贝内特逻辑深度的新表述。在Jordon和Moser先前发表的工作中，检查并比较了有限状态深度和下降深度的概念。这些分别基于有限状态换能器和无损下推压缩器。不幸的是，没有建立两个概念之间的完全分离。本文介绍了基于下降深度的Unary-stack Puspdown压缩机的新公式。这种改进的公式使我们能够通过证明具有高有限态深度和低俯卧撑深度的序列的存在，对其进行了完整的比较，反之亦然。还引入了基于LEMPEL-ZIV 78算法的新概念。通过证明存在不是有限状态深的Lempel-Ziv深层序列的存在，反之亦然，反之亦然。 LEMPEL-ZIV深度与下降深度的差异通过构建序列显示，其序列的序列大约为$ 1/2 $，但LEMPEL-ZIV深度低，并且具有较高的Lempel-Ziv深度但低点深度的序列。还讨论并证明了所有三个概念的属性。
This paper expands upon existing and introduces new formulations of Bennett's logical depth. In previously published work by Jordon and Moser, notions of finite-state depth and pushdown depth were examined and compared. These were based on finite-state transducers and information lossless pushdown compressors respectively. Unfortunately a full separation between the two notions was not established. This paper introduces a new formulation of pushdown depth based unary-stack pushdown compressors. This improved formulation 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 introduced. Its difference from finite-state depth is shown by demonstrating the existence of 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 level of roughly $1/2$ but low Lempel-Ziv depth, and a sequence with high Lempel-Ziv depth but low pushdown depth. Properties of all three notions are also discussed and proved.
