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)
Model of Computation
Parallel Computer
Lower Bound
Related Publications
(2)
Upper Bounds on the Computational Power of an Optical Model of Computation
Computational complexity of an optical model of computation
Subscribe
Academic
Publications
Lower bounds on the computational power of an optical model of computation
Edit
Lower bounds on the computational power of an optical model of computation
(
Citations: 10
)
BibTex
|
RIS
|
RefWorks
Download
Damien Woods
,
J. Paul Gibson
We present lower bounds on the computational power of an optical
model of computation
called theC2-CSM. We show thatC2-CSM time is at least as powerful as sequential space, thus giving one of the two inclusions that are necessary to show that the model veries the parallel computation thesis. Furthermore we show that C2-CSMs that simultaneously use polynomial space and polylogarithmic time decide at least the class NC.
Journal:
Natural Computing - NC
, vol. 7, no. 1, pp. 95-108, 2008
DOI:
10.1007/s11047-007-9039-7
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.cs.ucc.ie
)
(
www-public.it-sudparis.eu
)
(
www.bcri.ucc.ie
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.bcri.ucc.ie
)
(
dx.doi.org
)
(
www.cs.us.es
)
(
www-public.int-evry.fr
)
(
www.informatik.uni-trier.de
)
More »
Citation Context
(4)
...The machine implements a continuous space memory, instead of conventional computers digital memory [
11
]...
...Basic machine operations are defined according to Fourier optics [
11
] and some efforts are done to implement the machine [12]...
Sama Goliaei
,
et al.
An Optical Wavelength-Based Solution to the 3SAT Problem
...Our research is in the non-traditional direction, similar to e.g., [3,27,26,23,31,9,
34
,33,6,2], attempting to develop entirely new methods of computing that are not physically possible with electronics, and truly exploit the full parallel capabilities of light beams...
Shlomi Dolev
,
et al.
Optical Designs for Non-deterministic Turing Machines
...We have given upper [24] and lower [
26
] bounds on the computational power of the C2-CSM by showing that it verifies the parallel computation thesis...
Damien Woods
,
et al.
Lower bounds on the computational power of an optical model of computa...
...We have given lower bounds on the computational power of the C2-CSM by showing that it is at least as powerful as models that verify the parallel computation thesis [26,
29
]...
...Using this fact we nd that C2-CSMs that simultaneously use polynomial space and polylogarithmic time accept the class NC. Corollary 1 ([26,
29
])...
...3 This is in contrast to the proof of the previous lower bound proof [26,
29
] where...
...In previous work [26,
29
] we used an image with value/range of k (and thus of dyRange k) as a counter for k iterations...
Damien Woods
.
Optical Computing and Computational Complexity
References
(30)
Limits to Parallel Computation: P-Completeness Theory
(
Citations: 221
)
RAYMOND GREENLAW
,
H. JAMES HOOVER
Published in 1995.
Parallel Algorithms for Shared-Memory Machines
(
Citations: 389
)
Richard M. Karp
,
Vijaya Ramachandran
Published in 1990.
Continuous-space model of computation is Turing universal
(
Citations: 11
)
Thomas J. Naughton
Conference:
Storage and Retrieval for Image and Video Databases
, 2000
On the Computational Power of a Continuous-Space Optical Model of Computation
(
Citations: 17
)
Thomas J. Naughton
,
Damien Woods
Conference:
Machines, Computations, and Universality - MCU
, pp. 288-299, 2001
A characterization of the power of vector machines
(
Citations: 58
)
Vaughan R. Pratt
,
Michael O. Rabin
,
Larry J. Stockmeyer
Conference:
ACM Symposium on Theory of Computing - STOC
, pp. 122-134, 1974
Order by:
Citations
(10)
Optical solution for hard on average #P-complete instances (using exponential space for solving instances of the permanent)
(
Citations: 3
)
Amir Anter
,
Shlomi Dolev
Journal:
Natural Computing - NC
, vol. 9, no. 4, pp. 891-902, 2010
An Optical Wavelength-Based Solution to the 3SAT Problem
(
Citations: 3
)
Sama Goliaei
,
Saeed Jalili
Published in 2009.
Optical Designs for Non-deterministic Turing Machines
Shlomi Dolev
,
Yuval Nir
Published in 2009.
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.