Pushdown dimension

DOI10.1016/J.TCS.2007.04.005zbMATH Open1188.68172OpenAlexW2913798415MaRDI QIDQ995564FDOQ995564

Authors David Doty, Jared Nichols 

Publication date 3 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0504047

zbMATH Keywords

martingaleresource-bounded dimensionfinite-statepushdown

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• Bounded pushdown dimension vs Lempel Ziv information density
• scientific article; zbMATH DE number 1754653
• Finite-state dimension
• On the difference between finite-state and pushdown depth
• Dimension in Complexity Classes

Cites Work

• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3941840 (Why is no real title available?)
• scientific article; zbMATH DE number 2040326 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• A note on dimensions of polynomial size circuits
• Compression of individual sequences via variable-rate coding
• Dimension Characterizations of Complexity Classes
• Dimension in Complexity Classes
• Endliche Automaten und Zufallsfolgen
• Entropy rates and finite-state dimension
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Finite-state dimension
• Fractal dimension and logarithmic loss unpredictability.
• Fundamentals of Computation Theory
• Logical Approaches to Computational Barriers
• MAX3SAT is exponentially hard to approximate if NP has positive dimension.
• Mathematical Foundations of Computer Science 2005
• Mathematical Foundations of Computer Science 2005
• On encoding and decoding with two-way head machines
• Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• Partial bi-immunity, scaled dimension, and NP-completeness
• Prediction and dimension
• STACS 2004
• Scaled dimension and nonuniform complexity
• Selection functions that do not preserve normality
• The Construction of Decimals Normal in the Scale of Ten
• The dimensions of individual strings and sequences
• Two definitions of fractional dimension

Cited In (4)

• Mathematical Foundations of Computer Science 2005
• Pushdown and Lempel-Ziv depth
• On the difference between finite-state and pushdown depth
• Bounded pushdown dimension vs Lempel Ziv information density

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)