Tradeoff lower lounds for stack machines

DOI10.1007/S00037-012-0057-1MaRDI QIDQ744614zbMATH OpenOpenAlexFDO

Authors Matei David, Periklis A. Papakonstantinou

Publication date 25 September 2014

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-012-0057-1

zbMATH Keywords

lower boundreversalscommunication complexitystackTuring machinestreamingAuxPDAspace bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Tape versus queue and stacks: The lower bounds
• Communication-Space Tradeoffs for Unrestricted Protocols
• Trade-offs between communication and space
• Reversal complexity revisited
• Space Complexity of Stack Automata Models

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3560742 (Why is no real title available?)
• Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Communication Complexity
• Computational Complexity
• Lower bounds for randomized read/write stream algorithms
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On uniform circuit complexity
• P-uniform circuit complexity
• Properties that characterize LOGCFL
• Reversal Complexity
• Reversal complexity revisited
• Tally languages and complexity classes
• The space complexity of approximating the frequency moments
• Tree-size bounded alternation
• Two Applications of Inductive Counting for Complementation Problems
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

This page was built for publication: Tradeoff lower lounds for stack machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744614)