| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436808 | Theoretical Computer Science | 2007 | 19 Pages |
Abstract
Resource-bounded dimension is a notion of computational information density of infinite sequences based on computationally bounded gamblers. This paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. The pushdown dimension of any sequence is trivially bounded above by its finite-state dimension, since a pushdown gambler can simulate any finite-state gambler. We show that for every rational 0
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
