Machines, Computations, and Universality

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

344 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

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.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik
• ISBN: 9783540252610
• Sprache: Englisch
• Erscheinungsdatum: 08.03.2005
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Maurice Margenstern