Skip to main content
SpringerLink
Log in
Book cover

Machines, Computations, and Universality

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

  • Conference proceedings
  • © 2001

Overview

Editors:
  1. Maurice Margenstern

    1. LITA, UFR MIM, Université de Metz, Metz, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Yurii Rogozhin

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 2055)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (22 papers)

  1. Front Matter

    Pages I-VIII
    Download chapter 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
Back to top

Keywords

About this book

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.

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation