On pure space vs catalytic space

DOI10.1016/j.tcs.2022.04.005OpenAlexW4225522899MaRDI QIDQ5970816

Krishnamoorthy Dinesh, M. N. Jayalal Sarma, Sagar Bisoyi

Publication date: 23 May 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.005

zbMATH Keywords

lower boundscrossing sequencecatalytic computationkeywords space complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Limitations of incremental dynamic programming
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• Catalytic space: non-determinism and hierarchy
• Theory of computation.
• Communication Complexity
• Randomized and Symmetric Catalytic Computation
• Catalytic approaches to the tree evaluation problem
• Computing with a full memory
• On pure space vs catalytic space
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item