Skip to main content
  • Conference proceedings
  • © 2005

Machines, Computations, and Universality

4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers

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

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Conference series link(s): MCU: International Conference on Machines, Computations, and Universality

Conference proceedings info: MCU 2004.

Buy it now

Buying options

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

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

Table of contents (26 papers)

  1. Front Matter

  2. Invited Lectures

    1. On the Complexity of Universal Programs

      • Alain Colmerauer
      Pages 18-35
    2. Finite Sets of Words and Computing

      • Juhani Karhumäki
      Pages 36-49
    3. Universality and Cellular Automata

      • K. Sutner
      Pages 50-59
    4. Leaf Language Classes

      • Klaus W. Wagner
      Pages 60-81
  3. Selected Contributions

    1. Computational Completeness of P Systems with Active Membranes and Two Polarizations

      • Artiom Alhazov, Rudolf Freund, Gheorghe Păun
      Pages 82-92
    2. Computing with a Distributed Reaction-Diffusion Model

      • S. Bandini, G. Mauri, G. Pavesi, C. Simone
      Pages 93-103
    3. Computational Universality in Symbolic Dynamical Systems

      • Jean-Charles Delvenne, Petr Kůrka, Vincent D. Blondel
      Pages 104-115
    4. Real Recursive Functions and Real Extensions of Recursive Functions

      • Olivier Bournez, Emmanuel Hainry
      Pages 116-127
    5. Ordering and Convex Polyominoes

      • Giusi Castiglione, Antonio Restivo
      Pages 128-139
    6. Evolution and Observation: A Non-standard Way to Accept Formal Languages

      • Matteo Cavaliere, Peter Leupold
      Pages 153-163
    7. The Computational Power of Continuous Dynamic Systems

      • Jerzy Mycka, José Félix Costa
      Pages 164-175
    8. Is Bosco’s Rule Universal?

      • Kellie Michele Evans
      Pages 188-199
    9. Sequential P Systems with Unit Rules and Energy Assigned to Membranes

      • Rudolf Freund, Alberto Leporati, Marion Oswald, Claudio Zandron
      Pages 200-210
    10. Hierarchies of DLOGTIME-Uniform Circuits

      • Chuzo Iwamoto, Naoki Hatayama, Kenichi Morita, Katsunobu Imai, Daisuke Wakamatsu
      Pages 211-222
    11. Several New Generalized Linear- and Optimum-Time Synchronization Algorithms for Two-Dimensional Rectangular Arrays

      • Hiroshi Umeo, Masaya Hisaoka, Masato Teraoka, Masashi Maeda
      Pages 223-232
    12. Register Complexity of LOOP -, WHILE -, and GOTO -Programs

      • Markus Holzer, Martin Kutrib
      Pages 233-244

Other Volumes

  1. Machines, Computations, and Universality

Editors and Affiliations

  • IUT de Metz, LITA, Université Paul Verlaine - Metz, Metz, Cédex, France

    Maurice Margenstern

Bibliographic Information

Buy it now

Buying options

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