Author
|
Conference
|
Journal
|
Organization
|
Year
|
DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all domains
Limit my searches in the following domains
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Computational Complexity
Model of Computation
Growth Rate
Related Publications
(2)
An optical model of computation
Computational complexity of an optical model of computation
Subscribe
Academic
Publications
Complexity of Continuous Space Machine Operations
Edit
Complexity of Continuous Space Machine Operations
(
Citations: 7
)
BibTex
|
RIS
|
RefWorks
Download
Damien Woods
,
J. Paul Gibson
We investigate the
computational complexity
of an optical
model of computation
called the continuous space machine (CSM). We characterise worst case resource growth over time for each of the CSM's ten operations with respect to seven resource measures. Many operations exhibit unreasonably large growth rates thus motivating restrictions on the CSM, in particular we give a restriction called the C2-CSM.
Conference:
Conference on Computability in Europe - CIE
, pp. 540-551, 2005
DOI:
10.1007/11494645_66
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www-public.int-evry.fr
)
(
www.cs.ucc.ie
)
(
www.cs.us.es
)
(
www-public.it-sudparis.eu
)
(
www.informatik.uni-trier.de
)
(
dx.doi.org
)
(
www.bcri.ucc.ie
)
More »
Citation Context
(7)
...Also, the growth in resource usage was shown for each CSM operation, which in some cases was unreasonably large [14,
15
]...
...In [14,
15
] we dened theC2-CSM, a restricted class of CSM...
Damien Woods
,
et al.
Lower bounds on the computational power of an optical model of computa...
...A less restricted CSM definition [20,35] was shown to be too general for proving reasonable upper bounds on its computational power [
33
], so in this paper we mostly focus on computational complexity results for a restricted CSM called the C2-CSM...
...Motivated by a desire to apply standard complexity theory tools to the model, we defined [30,
33
] the C2-CSM, a restricted class of CSM...
...We have replaced the Fourier transform with the DFT [5], this essentially means that freq is now solely dependent on spatialRes; hence freq is not an interesting complexity measure for C2-CSMs and we do not analyse C2-CSMs in terms of freq complexity [30,
33
]...
Damien Woods
,
et al.
Parallel and Sequential Optical Computing
...We investigated the growth of complexity resources over time, with respect to CSM operations [26,
28
]...
...Some entries are immediate from the complexity measure denitions, for others proofs are given in the references [26,
28
]...
...Motivated by a desire to apply standard complexity theory tools to the model, we dened [26,
28
] the C2-CSM, a restricted and more realistic class of CSM...
...We have replaced the Fourier transform with the DFT [3], this essentially means that freq is now solely dependent on spatialRes; hence freq is not an interesting complexity measure for C2-CSMs and we do not analyse C2-CSMs in terms of freq complexity [26,
28
]...
Damien Woods
.
Optical Computing and Computational Complexity
...Much of the work presented here has appeared in published form [WN05,
WG05a
, WG05b, Woo, NW01]...
Damien Woods
.
Computational complexity of an optical model of computation
...The computational model we study is relatively new and is called the continuous space machine (CSM) [11, 12, 13, 20,
21
, 22, 23]...
...Also, the growth in resource usage was shown for each CSM operation, which in some cases was unreasonably large [
21
]...
...In earlier treatments [
21
, 23] we defined the complexity measures amplRes, phaseRes and freq. amplRes and phaseRes are measures of the cardinality of discrete amplitude and phase values of the complex numbers in the range of CSM images...
...In [
21
, 20] we defined the C2-CSM, a restricted and more realistic class of CSM...
Damien Woods
,
et al.
Upper Bounds on the Computational Power of an Optical Model of Computa...
References
(18)
Introduction to fourier optics
(
Citations: 2298
)
J. W. Goodman
Published in 1968.
The general purpose analog computer and recursive functions over the reals
(
Citations: 6
)
Unknown
Published in 2002.
Computational complexity of real valued recursive functions and analog circuits
(
Citations: 28
)
M. L. Campagnolo
Published in 2001.
Recursion Theory on the Reals and Continuous-Time Computation
(
Citations: 106
)
Cristopher Moore
Journal:
Theoretical Computer Science - TCS
, vol. 162, no. 1, pp. 23-44, 1996
Computable analysis: an introduction
(
Citations: 174
)
K. Weihrauch
Published in 2000.
Order by:
Citations
(7)
Lower bounds on the computational power of an optical model of computation
(
Citations: 10
)
Damien Woods
,
J. Paul Gibson
Journal:
Natural Computing - NC
, vol. 7, no. 1, pp. 95-108, 2008
Parallel and Sequential Optical Computing
(
Citations: 4
)
Damien Woods
,
Thomas J. Naughton
Published in 2008.
Optical Computing and Computational Complexity
(
Citations: 3
)
Damien Woods
Conference:
Unconventional Computing - UC
, pp. 27-40, 2006
Computational complexity of an optical model of computation
(
Citations: 9
)
Damien Woods
Published in 2005.
Upper Bounds on the Computational Power of an Optical Model of Computation
(
Citations: 6
)
Damien Woods
,
J. Paul Gibson
Conference:
International Symposium on Algorithms and Computation - ISAAC
, pp. 777-788, 2005