Unconventional Models of Computation, UMC’2K: Proceedings of the Second International Conference on Unconventional Models of Computation, (UMC’2K) ... Mathematics and Theoretical Computer Science)

This book contains papers presented at the 2nd International Conference on Unconventional Models of Computation (UMCK'2K), which was held at Solvay Institutes, Brussels, Belgium, in December 2000. Computers as we know them may be getting better and cheaper, and doing more for us, but they are still unable to cope with many tasks of practical interest. Nature, though, has been 'computing' with molecules and cells for billions of years, and these natural processes form the main motivation for the construction of radically new models of computation, the core theme of the papers in this volume. Unconventional Models of Computation, UMCK'2K covers all major areas of unconventional computation, including quantum computing, DNA-based computation, membrane computing and evolutionary algorithms. Front Matter....Pages I-X On the Ohya-Masuda Quantum SAT Algorithm....Pages 1-9 Computational Methods and Tools for Modeling and Analysis of Complex Processes....Pages 10-24 Quantum Recognizable Tree Functions....Pages 25-47 An Unconventional Computational Linear Algebra: Operator Trigonometry....Pages 48-67 Splicing Systems, Aqueous Computing, and Beyond....Pages 68-84 Some Methods of Computation in White Noise Calculus....Pages 85-93 Computing with Membranes: Attacking NP-Complete Problems....Pages 94-115 DNA Processing in Ciliates — The Wonders of DNA Computing in vivo ....Pages 116-118 Macroscopic Molecular Computation with Gene Networks....Pages 119-120 In Vitro Transcriptional Circuits....Pages 121-122 Parallelizing with Limited Number of Ancillae....Pages 123-134 Upper and Lower Bounds on Continuous-Time Computation....Pages 135-153 P Systems with Valuations....Pages 154-166 The Quantum Domain As a Triadic Relay....Pages 167-186 On P Systems with Active Membranes....Pages 187-201 Spatial Computing on Self-Timed Cellular Automata....Pages 202-214 Inaccessibility in Decision Procedures....Pages 215-233 On the Power of Nonlinear Mappings in Switching Map Systems....Pages 234-247 Quantum Information: The New Frontier....Pages 248-272 Quantum Computation Relative to Oracles....Pages 273-288 Solving NP-Complete Problems Using P Systems with Active Membranes....Pages 289-301 Back Matter....Pages 302-302