LEADER 07803nam 22008175 450 001 996200366603316 005 20230223023441.0 010 $a3-319-23111-1 024 7 $a10.1007/978-3-319-23111-2 035 $a(CKB)3890000000001365 035 $a(SSID)ssj0001558584 035 $a(PQKBManifestationID)16183748 035 $a(PQKBTitleCode)TC0001558584 035 $a(PQKBWorkID)14819483 035 $a(PQKB)11066420 035 $a(DE-He213)978-3-319-23111-2 035 $a(MiAaPQ)EBC6298992 035 $a(MiAaPQ)EBC5591312 035 $a(Au-PeEL)EBL5591312 035 $a(OCoLC)919735959 035 $a(PPN)188460713 035 $a(EXLCZ)993890000000001365 100 $a20150829d2015 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aMachines, Computations, and Universality$b[electronic resource] $e7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings /$fedited by Jerome Durand-Lose, Benedek Nagy 205 $a1st ed. 2015. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2015. 215 $a1 online resource (XX, 199 p. 41 illus.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9288 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-319-23110-3 320 $aIncludes bibliographical references and index. 327 $aIntro -- 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. 327 $a4 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. 327 $aA 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. 330 $aThis 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.). 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v9288 606 $aAlgorithms 606 $aComputer science 606 $aMachine theory 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aAlgorithms 606 $aTheory of Computation 606 $aFormal Languages and Automata Theory 606 $aComputer Science Logic and Foundations of Programming 606 $aDiscrete Mathematics in Computer Science 615 0$aAlgorithms. 615 0$aComputer science. 615 0$aMachine theory. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 14$aAlgorithms. 615 24$aTheory of Computation. 615 24$aFormal Languages and Automata Theory. 615 24$aComputer Science Logic and Foundations of Programming. 615 24$aDiscrete Mathematics in Computer Science. 676 $a004 702 $aDurand-Lose$b Jerome$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aNagy$b Benedek$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996200366603316 996 $aMachines, Computations, and Universality$9772227 997 $aUNISA