scientific article; zbMATH DE number 2040917

zbMATH Open1037.68060MaRDI QIDQ4452073FDOQ4452073

Till Tantau, Lane A. Hemaspaandra, Proshanto Mukherji

Publication date: 11 February 2004

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

Title of this publication is not available (Why is that?)

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

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)

Cited In (3)

• Mapping Computation with No Memory
• Lower bound technique for length-reducing automata
• 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)