Lower bounds on the computational power of an optical model of computation

• Arsenault HH, Sheng Y (1992) An introduction to optics in computers, volume TT 8 of Tutorial texts in optical engineering. SPIE

• Balcázar JL, Díaz J, Gabarró J (1988) Structural complexity, vols I and II. EATCS monographs on theoretical computer science. Springer, Berlin

  Google Scholar 

• Caulfield HJ (1990) Space-time complexity in optical computing. In: Javidi B (ed) Optical information-processing systems and architectures II, vol 1347. SPIE, pp 566–572

• Chandra AK, Stockmeyer LJ (1976) Alternation. In: 17th annual symposium on foundations of computer science. IEEE. Preliminary Version, Houston, Texas, pp 777–788

• Feitelson DG (1988) Optical computing: a survey for computer scientists. MIT Press

• Goldschlager LM (1977) Synchronous parallel computation. PhD thesis, University of Toronto, Computer Science Department

• Goodman JW (1996) Introduction to Fourier optics, 2nd edn. McGraw-Hill, New York

  Google Scholar 

• Greenlaw R, Hoover HJ, Ruzzo WL (1995) Limits to parallel computation: P-completeness theory. Oxford university Press, Oxford

  MATH  Google Scholar 

• Karp RM, Ramachandran V (1990) Parallel algorithms for shared memory machines, vol A. Elsevier, Amsterdam

  Google Scholar 

• Lee JN (ed) (1995) Design issues in optical processing. Cambridge studies in modern optics. Cambridge University Press

• Louri A, Post A (1992) Complexity analysis of optical-computing paradigms. Appl Opt 31(26):5568–5583

  Article  Google Scholar 

• McAulay AD (1991) Optical computer architectures. Wiley

• Naughton T, Javadpour Z, Keating J, Klíma M, Rott J (1999) General-purpose acousto-optic connectionist processor. Opt Eng 38(7):1170–1177

  Article  Google Scholar 

• Naughton TJ (2000a) Continuous-space model of computation is Turing universal. In: Bains S, Irakliotis LJ (eds) Critical technologies for the future of computing, proceedings of SPIE, vol 4109. San Diego, California, pp 121–128

• Naughton TJ (2000b) A model of computation for Fourier optical processors. In: Lessard RA, Galstian T (eds) Optics in computing 2000, Proc. SPIE, vol. 4089. Quebec, Canada, pp 24–34

• Naughton TJ, Woods D (2001) On the computational power of a continuous-space optical model of computation. In: Margenstern M, Rogozhin Y (eds) Machines, computations and universality: third international conference (MCU’01), vol 2055 of LNCS. Springer, Chişinău, Moldova, pp 288–299

• Parberry I (1987) Parallel complexity theory. Wiley

• Pratt VR, Rabin MO, Stockmeyer LJ (1974) A characterisation of the power of vector machines. In: Proc. 6th annual ACM symposium on theory of computing. ACM press, pp 122–134

• Pratt VR, Stockmeyer LJ (1976) A characterisation of the power of vector machines. J Comput Syst Sci 12:198–221

  MATH  MathSciNet  Google Scholar 

• Reif JH, Tyagi A (1997) Efficient parallel algorithms for optical computing with the discrete Fourier transform (DFT) primitive. Appl Opt 36(29):7327–7340

  Article  Google Scholar 

• van Emde Boas P (1990) Machine models and simulations. In: van Leeuwen J (ed) Handbook of theoretical computer science, vol A, chap 1. Elsevier, Amsterdam

• VanderLugt A (1992) Optical signal processing. Wiley Series in Pure and Applied Optics. Wiley, New York

  Google Scholar 

• Woods D (2005a) Computational complexity of an optical model of computation. PhD thesis, National University of Ireland, Maynooth

• Woods D (2005b) Upper bounds on the computational power of an optical model of computation. In: Deng X, Du D (eds) 16th international symposium on algorithms and computation (ISAAC 2005), vol 3827 of LNCS. Springer, Sanya, China, pp 777–788

• Woods D, Gibson JP (2005a) Complexity of continuous space machine operations. In: Cooper SB, Löewe B, Torenvliet L (eds) New computational paradigms, First conference on computability in Europe (CiE 2005), vol 3526 of LNCS. Springer, Amsterdam, pp 540–551

• Woods D, Gibson JP (2005b) Lower bounds on the computational power of an optical model of computation. In: Calude CS, Dinneen MJ, Păun G, Pérez-Jiménez MJ, Rozenberg G (eds) Fourth international conference on unconventional computation (UC’05), vol 3699 of LNCS. Springer, Sevilla, pp 237–250

• Woods D, Naughton TJ (2005) An optical model of computation. Theor Comput Sci 334(1–3):227–258

  Article  MATH  MathSciNet  Google Scholar 

• Yu FTS, Jutamulia S, Yin S (eds) (2001) Introduction to information optics. Academic Press

Download references