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 :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3628269
