Computation with absolutely no space overhead

DOI10.1007/3-540-45007-6_26MaRDI QIDQ4452073zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau

Publication date 11 February 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2710/27100325.htm

zbMATH Keywords

context-free languagescontext-sensitive languagesdeterministic linear languageslinear spacemetalinear languagesoverhead-free computationspace overheadspace reuseTuring machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Context-free languages can be accepted with absolutely no space overhead
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• scientific article; zbMATH DE number 3984575
• The problem of space invariance for sequential machines
• Computing with sublogarithmic space

Cited in

(3)

• Lower bound technique for length-reducing automata
• Context-free languages can be accepted with absolutely no space overhead
• Mapping Computation with No Memory

This page was built for publication: Computation with absolutely no space overhead

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