Finite-state dimension | |
Dai, JJ ; Lathrop, JI ; Lutz, JH ; Mayordomo, E | |
2004 | |
关键词 | bounded-depth circuit finite-state compressor finite-state dimension finite-state gambler gale Hausdorff dimension information-lossless compressor martingale normal sequence KOLMOGOROV COMPLEXITY INDIVIDUAL SEQUENCES HAUSDORFF |
英文摘要 | Classical Hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. The theorem of Eggleston (Quart. J. Math. Oxford Ser. 20 (1949) 31-36) relating Hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). Every rational sequence has finite-state dimension 0, but every rational number in [0,1] is the finite-state dimension of a sequence in the low-level complexity class AC(0). Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors. (C) 2003 Published by Elsevier B.V.; Computer Science, Theory & Methods; SCI(E); EI; 37; ARTICLE; 1-3; 1-33; 310 |
语种 | 英语 |
出处 | EI ; SCI |
出版者 | 理论计算机科学 |
内容类型 | 其他 |
源URL | [http://hdl.handle.net/20.500.11897/255752] |
专题 | 数学科学学院 |
推荐引用方式 GB/T 7714 | Dai, JJ,Lathrop, JI,Lutz, JH,et al. Finite-state dimension. 2004-01-01. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论