Overhead-Free Computation, DCFLs, and CFLs
<|reference_start|>Overhead-Free Computation, DCFLs, and CFLs: We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space.   Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.<|reference_end|>
@article{hemaspaandra2004overhead-free,
    title={Overhead-Free Computation, DCFLs, and CFLs},
    author={Lane A. Hemaspaandra, Proshanto Mukherji, and Till Tantau},
    journal={arXiv preprint arXiv:cs/0410035},
    year={2004},
    number={URCS-TR-2004-844},
    archivePrefix={arXiv},
    eprint={cs/0410035},
    primaryClass={cs.CC}
}