Machines, Computations, and Universality [[electronic resource] ] : 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings / / edited by Jerome Durand-Lose, Benedek Nagy

• Record Nr.: UNISA996200366603316
• Pubbl/distr/stampa: Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015
• ISBN: 3-319-23111-1
• Edizione: [1st ed. 2015.]
• Descrizione fisica: 1 online resource (XX, 199 p. 41 illus.)
• Collana: Theoretical Computer Science and General Issues, , 2512-2029 ; ; 9288
• Disciplina: 004
• Soggetti: Algorithms; Computer science; Machine theory; Computer science—Mathematics; Discrete mathematics; Theory of Computation; Formal Languages and Automata Theory; Computer Science Logic and Foundations of Programming; Discrete Mathematics in Computer Science
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: 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.
• Sommario/riassunto: This book constitutes the refereed proceedings of the 7th International Conference on Machines, Computations, and Universality, MCU 2015, held in Famagusta, North Cyprus, in September 2015. The 10 revised full papers presented together with 4 invited talks were carefully ; reviewed and selected from 23 submissions. MCU explores computation in the setting of various discrete models (Turing machines, register machines, cellular automata, tile assembly systems, rewriting systems, molecular computing models, neural models, etc.) and analog and hybrid models (BSS machines, infinite time cellular automata, real machines, quantum computing, etc.).