Context-free languages can be accepted with absolutely no space overhead
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 overhead-free 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. (c) 2005 Elsevier Inc. All rights reserved.
context-free languages space overhead linear space deterministic context-free languages editing turing machines in-place algorithms overhead-free computation restarting automata rrw-automata space reuse two-stack automata