Overview

This book constitutes the thoroughly refereed postproceedings of the 4th International Conference on Machines, Computations, and Universality, MCU 2004, held in Saint Petersburg, Russia in September 2004.The 21 revised full papers presented together with 5 invited papers went through two rounds of reviewing, selection, and improvement. A broad variety of foundational aspects in theoretical computer science are addressed, such as cellular automata, molecular computing, quantum computing, formal languages, automata theory, Turing machines, P systems, etc.

Full Product Details

Author:   Maurice Margenstern
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   2005 ed.
Volume:   3354
Dimensions:   Width: 15.20cm , Height: 1.80cm , Length: 22.90cm
Weight:   1.070kg
ISBN:  

9783540252610

ISBN 10:   3540252614
Pages:   328
Publication Date:   08 March 2005
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

Invited Lectures.- Algorithmic Randomness, Quantum Physics, and Incompleteness.- On the Complexity of Universal Programs.- Finite Sets of Words and Computing.- Universality and Cellular Automata.- Leaf Language Classes.- Selected Contributions.- Computational Completeness of P Systems with Active Membranes and Two Polarizations.- Computing with a Distributed Reaction-Diffusion Model.- Computational Universality in Symbolic Dynamical Systems.- Real Recursive Functions and Real Extensions of Recursive Functions.- Ordering and Convex Polyominoes.- Subshifts Behavior of Cellular Automata. Topological Properties and Related Languages.- Evolution and Observation: A Non-standard Way to Accept Formal Languages.- The Computational Power of Continuous Dynamic Systems.- Abstract Geometrical Computation for Black Hole Computation.- Is Bosco’s Rule Universal?.- Sequential P Systems with Unit Rules and Energy Assigned to Membranes.- Hierarchies of DLOGTIME-Uniform Circuits.- Several New Generalized Linear- and Optimum-Time Synchronization Algorithms for Two-Dimensional Rectangular Arrays.- Register Complexity of LOOP-, WHILE-, and GOTO-Programs.- Classification and Universality of Reversible Logic Elements with One-Bit Memory.- Universal Families of Reversible P Systems.- Solving 3CNF-SAT and HPP in Linear Time Using WWW.- Completing a Code in a Regular Submonoid of the Free Monoid.- On Computational Universality in Language Equations.- Attacking the Common Algorithmic Problem by Recognizer P Systems.- On the Minimal Automaton of the Shuffle of Words and Araucarias.

Reviews

Author Information

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions