Machines, Computations, and Universality: 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers

Front Cover
Springer Science & Business Media, Mar 8, 2005 - Computers - 327 pages
In this volume, the reader will ?rst?nd the invited talks givenatthe conference. Then, in a second part, he/she will ?nd the contributions which were presented attheconferenceafterselection.Inbothcases, papersaregiveninthealphabetic order of the authors. MCU 2004 was the fourth edition of the conference in theoretical computer science, Machines, Computations and Universality, formerly, Machines etcalculs universels. The ?rst and the second editions, MCU 1995 and MCU 1998, were organized by Maurice Margenstern, respectively in Paris and in Metz (France). The third edition, MCU 2001, was the ?rst one to be organized outside France and it was held in Chi, sin? au (Moldova). Its co-organizers were Maurice Marg- sternandYuriiRogozhin.TheproceedingsofMCU2001werethe?rstto appear in Lecture Notes in Computer Science, see LNCS 2055. From its very beginning, the MCU conference has been an international s- enti?c event. For the fourth edition, Saint Petersburg was chosen to hold the meeting. The success of the meeting con?rmed that the choice was appropriate. MCU 2004 also aimed at high scienti?c standards. We hope that this v- ume will convince the reader that this tradition of the previous conferences was also upheld by this one. Cellular automata and molecular computing are well represented in this volume. And this is the case for quantum computing, formal languages and the theory of automata too. MCU 2004 also did not fail its tra- tion to provide our community with important results on Turing machines. Also a new feature of the Saint Petersburg edition was the contributions on analog models and the presence of unconventional models.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Algorithmic Randomness Quantum Physics and Incompleteness
1
On the Complexity of Universal Programs
18
Finite Sets of Words and Computing
36
Universality and Cellular Automata
50
Leaf Language Classes
60
Computational Completeness of P Systems with Active Membranes and Two Polarizations
82
Computing with a Distributed ReactionDiffusion Model
93
Computational Universality in Symbolic Dynamical Systems
104
Is Boscos Rule Universal?
188
Sequential P Systems with Unit Rules and Energy Assigned to Membranes
200
Hierarchies of DLOGTIMEUniform Circuits
211
Several New Generalized Linear and OptimumTime Synchronization Algorithms for TwoDimensional Rectangular Arrays
223
Register Complexity of LOOP WHILE and GOTOPrograms
233
Classification and Universality of Reversible Logic Elements with OneBit Memory
245
Universal Families of Reversible P Systems
257
Solving 3CNFSAT and HPP in Linear Time Using WWW
269

Real Recursive Functions and Real Extensions of Recursive Functions
116
Ordering and Convex Polyominoes
128
Subshifts Behavior of Cellular Automata Topological Properties and Related Languages
140
A Nonstandard Way to Accept Formal Languages
153
The Computational Power of Continuous Dynamic Systems
164
Abstract Geometrical Computation for Black Hole Computation
176
Completing a Code in a Regular Submonoid of the Free Monoid
281
On Computational Universality in Language Equations
292
Attacking the Common Algorithmic Problem by Recognizer P Systems
304
On the Minimal Automaton of the Shuffle of Words and Araucarias
316
Author Index
328
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information