Pushdown dimension
| dc.creator | Doty, David | |
| dc.creator | Nichols, Jared | |
| dc.date | 2005-04-12 | |
| dc.date | 2005-05-27 | |
| dc.date.accessioned | 2026-07-07T08:15:25Z | |
| dc.date.available | 2026-07-07T08:15:25Z | |
| dc.description | This paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. Pushdown dimension is trivially bounded above by finite-state dimension for all sequences, since a pushdown gambler can simulate any finite-state gambler. We show that for every rational 0 < d < 1, there exists a sequence with finite-state dimension d whose pushdown dimension is at most d/2. This establishes a quantitative analogue of the well-known fact that pushdown automata decide strictly more languages than finite automata. | |
| dc.description | 10 page main body; 12 page appendix of proofs | |
| dc.identifier | https://arxiv.org/abs/cs/0504047 | |
| dc.identifier | http://arxiv.org/abs/cs/0504047 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133443 | |
| dc.subject | Information Theory | |
| dc.subject | Computational Complexity | |
| dc.title | Pushdown dimension | |
| dc.type | text |