scientific article; zbMATH DE number 2040917

zbMATH Open1037.68060MaRDI QIDQ4452073FDOQ4452073

Authors Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau

Publication date 11 February 2004

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

zbMATH Keywords

context-free languageslinear spaceTuring machinescontext-sensitive languagesspace overheadmetalinear languagesdeterministic linear languagesoverhead-free computationspace reuse

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
• scientific article; zbMATH DE number 1072535

Cited in

(3)

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

This page was built for publication:

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