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 definition and its applications, International Journal of Computers and Applications, 25(4), 2003, 247–257.
  2. [2] H. Yamada, Real-time computation and recursive functions not real-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: An infinite hierarchy for parallel real-time systems, Theory of Computing Systems, 34(6), 2001, 565–576.
  4. [4] S.G. Akl & S.D. Bruda, Parallel real-time optimization: Beyond speedup, 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 computation handbook (Boca Raton, FL: CRC Press LLC, 1999), 27-1–27-23.
  6. [6] Y. Ben-Asher, K.-J. Lange, D. Peleg, & A. Schuster, The complexity of reconfiguring network models, Information and Computation, 121, 1995, 41–58. doi:10.1006/inco.1995.1122
  7. [7] J.L. Trahan, R. Vaidyanathan, & R.K. Thiruchelvan, On the power of segmenting and fusing buses, Journal of Parallel and Distributed Computing, 34, 1996, 82–94. doi:10.1006/jpdc.1996.0047
  8. [8] J.P. Gray & T.A. Kean, Configurable hardware: A new paradigm for computation, in C.L. Seitz (Ed.), Proc. of the 10th Carltech Conf. on VLSI (Cambridge, MA: MIT Press, March 1989), 279–295.
  9. [9] J.L. Trahan, R. Vaidyanathan, & C.P. Subbaraman, Constant time graph algorithms on the reconfigurable multiple bus machine, 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 Information Science, Queen’s University, January 2001.
  11. [11] R. Greenlaw, H.J. Hoover, & W.L. Ruzo, Limits to Parallel Computation: P-Completeness Theory (New York: Oxford University 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 decision programs computationally equivalent?, Proc. 17th Annual ACM Symp. on Theory of Computing (New York, NY: ACM Press, December 1985), 464–475.
  14. [14] R. Kannan & B. Korte, Approximative combinatorial algorithms, in R.W. Cottle, M.L. Kelmanson, & B. Korte (Eds.), Mathematical Programming (Amsterdam, The Nederlands: Elsevier Science Publishers, 1981), 195–248.
  15. [15] T.H. Cormen, C.E. Leiserson, & C. Stein, Introduction to Algorithms, Second Edition (Cambridge, MA: MIT Press, 2001).
  16. [16] S.G. Akl, Parallel computation: models and methods (Upper Saddle River, NJ: Prentice-Hall, 1997).

Important Links:

Go Back