Machines, Computations, and Universality

1. Front Matter

   Pages I-VIII

   PDF

2. Invited Lectures Notes

   1. Three Small Universal Turing Machines

      • Claudio Baiocchi

      Pages 1-10

   2. Computation in Gene Networks

      • Asa Ben-Hur, Hava T. Siegelmann

      Pages 11-24

   3. Power, Puzzles and Properties of Entanglement

      • Jozef Gruska, Hiroshi Imai

      Pages 25-68

   4. Combinatorial and Computational Problems on Finite Sets of Words

      • Juhani Karhumäki

      Pages 69-81

   5. Computing with Membranes (P Systems): Universality Results

      • Carlos Martín-Vide, Gheorghe PĂun

      Pages 82-101

   6. A Simple Universal Logic Element and Cellular Automata for Reversible Computing

      • Kenichi Morita

      Pages 102-113

   7. Some Applications of the Decidability of DPDA’s Equivalence

      • Géraud Sénizergues

      Pages 114-132

   8. The Equivalence Problem for Computational Models: Decidable and Undecidable Cases

      • Vladimir A. Zakharov

      Pages 133-152

   9. Two Normal Forms for Rewriting P Systems

      • Claudio Zandron, Claudio Ferretti, Giancarlo Mauri

      Pages 153-164

3. Technical Contributions

   1. On a Conjecture of Kůrka. A Turing Machine with No Periodic Configurations

      • Vincent D. Blondel, Julien Cassaigne, Codrin Nichitiu

      Pages 165-176

   2. On the Transition Graphs of Turing Machines

      • Didier Caucal

      Pages 177-189

4. JC-Nets

   1. JC-Nets

      • Gabriel Ciobanu, Mihai Rotaru

      Pages 190-201

5. Nonterminal Complexity of Programmed Grammars

   1. Nonterminal Complexity of Programmed Grammars

      • Henning Fernau

      Pages 202-213

6. On the Number of Non-Terminal Symbols in Graph-Controlled, Programmed and Matrix Grammars

   1. On the Number of Non-Terminal Symbols in Graph-Controlled, Programmed and Matrix Grammars

      • Rudolf Freund, Gheorghe Păun

      Pages 214-225

7. A Direct Construction of a Universal Extended H System

   1. A Direct Construction of a Universal Extended H System

      • Pierluigi Frisco

      Pages 226-239

8. Speeding-Up Cellular Automata by Alternations

   1. Speeding-Up Cellular Automata by Alternations

      • Chuzo Iwamoto, Katsuyuki Tateishi, Kenichi Morita, Katsunobu Imai

      Pages 240-251

9. Efficient Universal Pushdown Cellular Automata and Their Application to Complexity

   1. Efficient Universal Pushdown Cellular Automata and Their Application to Complexity

      • Martin Kutrib

      Pages 252-263

10. Firing Squad Synchronization Problem on Bidimensional Cellular Automata with Communication Constraints

    1. Firing Squad Synchronization Problem on Bidimensional Cellular Automata with Communication Constraints

       • Salvatore La Torre, Margherita Napoli, Mimmo Parente

       Pages 264-275

11. P Systems with Membrane Creation: Universality and Efficiency

    1. P Systems with Membrane Creation: Universality and Efficiency

       • Madhu Mutyam, Kamala Krithivasan

       Pages 276-287

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.

• DNA computing
• Reversible Computing
• Theoretical computer science
• Turing machines
• automata
• automata theory
• cellular automata
• complexity
• computational complexity
• decidability
• formal language
• formal languages
• grammars
• logic
• quantum computing
• algorithm analysis and problem complexity

• LITA, UFR MIM, Université de Metz, Metz, France

  Maurice Margenstern

• Institute of Mathematics and Computer Science of the Academy of Sciences of Moldova, Chiŗinău

  Yurii Rogozhin

Policies and ethics