DocumentCode
3628269
Title
A time-space tradeoff for language recongnition
Author
Pavol Duris;Zvi Galil
fYear
1981
Firstpage
53
Lastpage
57
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.
Keywords
"Magnetic heads","Costs","Petroleum","Tiles","Sorting","Multidimensional systems","Upper bound","Space charge","Testing"
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1981. SFCS ´81. 22nd Annual Symposium on
ISSN
0272-5428
Type
conf
DOI
10.1109/SFCS.1981.9
Filename
4568316
Link To Document