Pushdown dimension
From MaRDI portal
Publication:995564
DOI10.1016/J.TCS.2007.04.005zbMATH Open1188.68172arXivcs/0504047OpenAlexW2913798415MaRDI QIDQ995564FDOQ995564
Authors: David Doty, Jared Nichols 
Publication date: 3 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/cs/0504047
Recommendations
Cites Work
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
- Two definitions of fractional dimension
- Finite-state dimension
- The dimensions of individual strings and sequences
- Selection functions that do not preserve normality
- Endliche Automaten und Zufallsfolgen
- Compression of individual sequences via variable-rate coding
- Entropy rates and finite-state dimension
- Title not available (Why is that?)
- The Construction of Decimals Normal in the Scale of Ten
- Title not available (Why is that?)
- Title not available (Why is that?)
- Logical Approaches to Computational Barriers
- A Kolmogorov complexity characterization of constructive Hausdorff dimension.
- Dimension in Complexity Classes
- Fractal dimension and logarithmic loss unpredictability.
- Mathematical Foundations of Computer Science 2005
- MAX3SAT is exponentially hard to approximate if NP has positive dimension.
- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
- STACS 2004
- Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
- A note on dimensions of polynomial size circuits
- On encoding and decoding with two-way head machines
- Dimension Characterizations of Complexity Classes
- Partial bi-immunity, scaled dimension, and NP-completeness
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Mathematical Foundations of Computer Science 2005
- Prediction and dimension
- Scaled dimension and nonuniform complexity
- Title not available (Why is that?)
- Fundamentals of Computation Theory
Cited In (2)
This page was built for publication: Pushdown dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q995564)
