Machines, Computations, and Universality

Name: Machines, Computations, and Universality | 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings
Brand: Springer
Price: 50.28 EUR
Availability: OnlineOnly

7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings

Jerome Durand-Lose Benedek Nagy(Herausgeber*in)

Springer (Verlag)

Erschienen am 29. August 2015

XX, 199 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-23111-2 (ISBN)

50,28 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Invited Talks
Decidability Problems for Self-induced Systems Generated by a Substitution
Concurrency, Histories, and Nets
Spiking Neural P Systems: A Class of Parallel Computing Models Inspired by Neurons
Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics
Contents
Invited Papers
Decidability Problems for Self-induced Systems Generated by a Substitution
1 Substitutions Among Mathematics and Computer Science
2 The Geometry of One-Dimensional Substitutions
3 Undecidability of GIFS Topological Properties
4 Decidability of Rauzy Fractals Properties
5 Extending the Framework of Rauzy Fractals
References
Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics
1 Introduction
1.1 Geometrical Boosting of Computational Power
1.2 Geometrical Reduction of Computational Power
1.3 Geometrical Effects on Computational Complexity
2 Modelling Relativity Theory in Isabelle/HOL
2.1 First-Order Relativity Theory
2.2 Generating Verifiable Proofs
3 Next Steps
References
Regular Papers
A Connection Between Red-Green Turing Machines and Watson-Crick T0L Systems
1 Introduction
2 Preliminaries
2.1 Red-Green Turing Machines
2.2 Watson-Crick L Systems
3 Results
4 Conclusions
References
Tight Bounds for Cut-Operations on Deterministic Finite Automata
1 Introduction
2 Preliminaries
3 The Descriptional Complexity of the Cut Operation
4 The Descriptional Complexity of the Iterated-Cut Operation
5 Conclusions
References
Non-isometric Contextual Array Grammars with Regular Control and Local Selectors
1 Introduction
2 Definitions
3 Isometric Contextual Array Grammars
3.1 The Basic Variant
3.2 Contextual Array Grammars with Regular Control
4 Non-isometric Contextual Array Grammars
4.1 Non-isometric Contextual Array Grammars with Regular Control
4.2 Non-isometric Contextual Array Grammars with Regular Control and Local Selectors
5 A Characterization of Linear String Languages
6 More-Dimensional Non-isometric Contextual Array Grammars with Regular Control and Local Selectors
7 Conclusions
References
Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States
1 Introduction
2 Preliminaries
3 Universality Results
4 Conclusions
References
Tinput-Driven Pushdown Automata
1 Introduction
2 Preliminaries
3 Computational Capacity
4 Closure Properties
5 Decidability Questions
6 Representation Theorems
7 Conclusion
References
Reversible Limited Automata
1 Introduction
2 Preliminaries
3 Sweeping Reversible k-Limited Automata
4 A Hierarchy of Reversible Limited Automata
5 Limited Automata and Church-Rosser Languages
References
An Intrinsically Universal Family of Causal Graph Dynamics
1 Introduction
2 Graphs and Localizable Dynamics
3 Intrinsic Simulation and Universality
4 Preliminary Results
5 A Family of Intrinsically Universal Local Rules
5.1 Graph Encoding
5.2 Local Rule Encoding
5.3 Description of an Intrinsically Universal Rule
5.4 On the (non) Existence of a Single Universal Rule
6 Conclusion
References
The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems
1 Introduction
2 Definitions
2.1 Informal Definition of the 2HAM
2.2 Definitions for Simulation
2.3 Intrinsic Universality
3 Uniform Mappings
4 Strong Simulation via Uniform Mappings
5 Impossibility of Strong Simulation at Higher Temperatures
6 Simulating Arbitrary Lower Temperature Ladder Systems
References
A Characterization of NP Within Interval-Valued Computing
1 Introduction
1.1 Computing Paradigms
1.2 A Brief History of Interval-Valued Computing
2 Preliminaries
3 Interval-Valued Computations: Definitions
4 Results
5 Example
6 Conclusions, Further Remarks
References
Universality in Infinite Petri Nets
1 Introduction
2 Petri Nets and Linear Cellular Automata
3 Simulating Separate Cell
4 Simulating Cellular Automaton
5 Simulating TMs Which Simulate Rule 110
6 Some Remarks on Universal Constructs
7 Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken