Machines, Computations, and Universality

Produktdetails

Verlag

Springer Berlin Heidelberg
Springer-Verlag GmbH

Erschienen

2007

Sprache

English

Seiten

340

Infos

340 Seiten
235 mm x 155 mm

ISBN

978-3-540-74592-1

Inhaltsverzeichnis

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.