Loading [MathJax]/extensions/TeX/euler_ieee.js
A time-space tradeoff for language recongnition | IEEE Conference Publication | IEEE Xplore

A time-space tradeoff for language recongnition


Abstract:

We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.

Abstract:

We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.
Date of Conference: 28-30 October 1981
Date Added to IEEE Xplore: 18 July 2008
Print ISSN: 0272-5428
Conference Location: Nashville, TN, USA

Contact IEEE to Subscribe

References

References is not available for this document.