+612 9045 4394
Machines, Computations, and Universality : Third International Conference, McU 2001 Chisinau, Moldava, May 23-27, 2001 Proceedings - Maurice Margenstern

Machines, Computations, and Universality

Third International Conference, McU 2001 Chisinau, Moldava, May 23-27, 2001 Proceedings

By: Maurice Margenstern (Editor), Yurii Rogozhin (Editor)

Paperback Published: 9th May 2001
ISBN: 9783540421214
Number Of Pages: 328

Share This Book:


or 4 easy payments of $31.26 with Learn more
Ships in 5 to 9 business days

In the ?rst part of the present volume of LNCS, the reader will ?nd the invited talks given at the MCU 2001 conference. In the second part, he/she will ?nd the contributions that were presented at the conference after selection. In both cases, papers are arranged in the alphabetical order of the authors. MCU 2001 is the third conference in theoretical computer science, Machines, computations and universality, formerly, Machines et calculs universels. Both previous conferences, MCU'95 and MCU'98, were organized by Maurice M- genstern in Paris and in Metz (France), respectively. From the very beginning, MCU conferences have been an international sci- ti?c event. For the third conference, in order to stress that aspect, it was decided to hold it outside France. Moldova was chosen thanks to the close cooperation between the present chairmen of MCU 2001. MCU 2001 also aims at high scienti?c standards. We hope that the present volume will convince the reader that the tradition of previous conferences have been upheld by this one. Cellular automata and molecular computing are well represented in this volume. And this is also the case for quantum computing, f- mal languages, and the theory of automata. MCU 2001 does not fail its tradition of providing our community with important results on Turing machines.

Invited Lectures
Three Small Universal Turing Machinesp. 1
Computation in Gene Networksp. 11
Power, Puzzles and Properties of Entanglementp. 25
Combinatorial and Computational Problems on Finite Sets of Wordsp. 69
Computing with Membranes (P Systems): Universality Resultsp. 82
A Simple Universal Logic Element and Cellular Automata for Reversible Computingp. 102
Some Applications of the Decidability of DPDAÆs Equivalencep. 114
The Equivalence Problem for Computational Models: Decidable and Undecidable Casesp. 133
Two Normal Forms for Rewriting P Systemsp. 153
Technical Contributions
On a Conjecture of Kurka. A Turing Machine with No Periodic Configurationsp. 165
On the Transition Graphs of Turing Machinesp. 177
JC-Netsp. 190
Nonterminal Complexity of Programmed Grammarsp. 202
On the Number of Non-terminal Symbols in Graph-Controlled, Programmed and Matrix Grammarsp. 214
A Direct Construction of a Universal Extended H Systemp. 226
Speeding-Up Cellular Automata by Alternationsp. 240
Efficient Universal Pushdown Cellular Automata and Their Application to Complexityp. 252
Firing Squad Synchronization Problem on Bidimensional Cellular Automata with Communication Constraintsp. 264
P Systems with Membrane Creation: Universality and Efficiencyp. 276
On the Computational Power of a Continuous-Space Optical Model of Computationp. 288
On a P-optimal Proof System for the Set of All Satisfiable Boolean Formulas (SAT)p. 300
D0L System = Watson-Crick Complementarity=Universal Computationp. 308
Author Indexp. 321
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540421214
ISBN-10: 3540421211
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 328
Published: 9th May 2001
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 1.78
Weight (kg): 0.47