SIZE MATTERS: LOGARITHMIC SPACE IS REAL TIME

S.D. Bruda and S.G. Akl

References

  1. [1] S.D. Bruda & S.G. Akl, Real-time computation: A formal defi-nition and its applications, International Journal of Computersand Applications, 25(4), 2003, 247–257.
  2. [2] H. Yamada, Real-time computation and recursive functions notreal-time computable, IRE Trans. on Electronic Computers,EC-11, 1962, 753–760.
  3. [3] S.D. Bruda & S.G. Akl, Pursuit and evasion on a ring: Aninfinite hierarchy for parallel real-time systems, Theory ofComputing Systems, 34(6), 2001, 565–576.
  4. [4] S.G. Akl & S.D. Bruda, Parallel real-time optimization: Beyondspeedup, Parallel Processing Letters, 9, 1999, 499–509. doi:10.1142/S0129626499000463
  5. [5] E. Allender, M.C. Loui, & K.W. Regan, Complexity classes,in M.J. Atallah (Ed.), Algorithms and theory of computationhandbook (Boca Raton, FL: CRC Press LLC, 1999), 27-1–27-23.
  6. [6] Y. Ben-Asher, K.-J. Lange, D. Peleg, & A. Schuster, Thecomplexity of reconfiguring network models, Information andComputation, 121, 1995, 41–58. doi:10.1006/inco.1995.1122
  7. [7] J.L. Trahan, R. Vaidyanathan, & R.K. Thiruchelvan, On thepower of segmenting and fusing buses, Journal of Parallel andDistributed Computing, 34, 1996, 82–94. doi:10.1006/jpdc.1996.0047
  8. [8] J.P. Gray & T.A. Kean, Configurable hardware: A newparadigm for computation, in C.L. Seitz (Ed.), Proc. of the10th Carltech Conf. on VLSI (Cambridge, MA: MIT Press,March 1989), 279–295.
  9. [9] J.L. Trahan, R. Vaidyanathan, & C.P. Subbaraman, Constanttime graph algorithms on the reconfigurable multiple busmachine, Journal of Parallel and Distributed Computing, 46,1997, 1–14. doi:10.1006/jpdc.1997.1385
  10. [10] N. Nagy, The maximum flow problem: A real-time approach.Master’s thesis, Department of Computing and InformationScience, Queen’s University, January 2001.
  11. [11] R. Greenlaw, H.J. Hoover, & W.L. Ruzo, Limits to ParallelComputation: P-Completeness Theory (New York: OxfordUniversity Press, 1995).
  12. [12] A. Szepietowski, Turing Machines with Sublogarithmic Space,Springer Lecture Notes in Computer Science 843, 1994.
  13. [13] R.M. Karp, E. Upfal, & A. Wigderson, Are search and deci-sion programs computationally equivalent?, Proc. 17th AnnualACM Symp. on Theory of Computing (New York, NY: ACMPress, December 1985), 464–475.
  14. [14] R. Kannan & B. Korte, Approximative combinatorial algo-rithms, in R.W. Cottle, M.L. Kelmanson, & B. Korte (Eds.), Mathematical Programming (Amsterdam, The Nederlands: El-sevier Science Publishers, 1981), 195–248.
  15. [15] T.H. Cormen, C.E. Leiserson, & C. Stein, Introduction toAlgorithms, Second Edition (Cambridge, MA: MIT Press, 2001).
  16. [16] S.G. Akl, Parallel computation: models and methods (UpperSaddle River, NJ: Prentice-Hall, 1997).

Important Links:

Go Back