Machines, Computations, and Universality

5th International Conference, MCU 2007, Orleans, France, September 10-13, 2007, Proceedings

340 Seiten, Taschenbuch

Kurzbeschreibung des Verlags

Invited Talks.- Encapsulating Reaction-Diffusion Computers.- On the Computational Capabilities of Several Models.- Universality, Reducibility, and Completeness.- Using Approximation to Relate Computational Classes over the Reals.- A Survey of Infinite Time Turing Machines.- The Tiling Problem Revisited (Extended Abstract).- Decision Versus Evaluation in Algebraic Complexity.- A Universal Reversible Turing Machine.- P Systems and Picture Languages.- Regular Papers.- Partial Halting in P Systems Using Membrane Rules with Permitting Contexts.- Uniform Solution of QSAT Using Polarizationless Active Membranes.- Satisfiability Parsimoniously Reduces to the TantrixTM Rotation Puzzle Problem.- Planar Trivalent Network Computation.- On the Power of Networks of Evolutionary Processors.- Study of Limits of Solvability in Tag Systems.- Query Completeness of Skolem Machine Computations.- More on the Size of Higman-Haines Sets: Effective Constructions.- Insertion-Deletion Systems with One-Sided Contexts.- Accepting Networks of Splicing Processors with Filtered Connections.- Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata.- Four Small Universal Turing Machines.- Changing the Neighborhood of Cellular Automata.- A Simple P-Complete Problem and Its Representations by Language Equations.- Slightly Beyond Turing's Computability for Studying Genetic Programming.- A Smallest Five-State Solution to the Firing Squad Synchronization Problem.- Small Semi-weakly Universal Turing Machines.- Simple New Algorithms Which Solve the Firing Squad Synchronization Problem: A 7-States 4n-Steps Solution.

• Reihe: Lecture Notes in Computer Science
• Themen: Informatik und Informationstechnologie Informatik Theoretische Informatik
• ISBN: 9783540745921
• Sprache: Englisch
• Erscheinungsdatum: 23.08.2007
• Größe: 235 x 155 mm
• Verlag: Springer
• Herausgegeben von: Jérôme Durand-Lose, Maurice Margenstern