Overhead-Free Computation, DCFLs, and CFLs

Details Overhead-Free Computation, DCFLs, and CFLs Overhead-Free Computation, DCFLs, and CFLs

2004-10-15

arxiv.org/abs/cs/0410035v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Overhead-Free Computation, DCFLs, and CFLs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Overhead-Free Computation, DCFLs, and CFLs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Overhead-Free Computation, DCFLs, and CFLs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-289846