Margenstern Machines, Computations, and Universality

4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers
2005
ISBN: 978-3-540-31834-7
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 328 Seiten, eBook

Reihe: Theoretical Computer Science and General Issues

Zielgruppe

Research

Autoren/Hrsg.

Margenstern, Maurice

Inhaltsverzeichnis

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.