nach oben

Natural Computing

Erschienen in:

25.11.2019

Hierarchies and undecidability results for iterative arrays with sparse communication

verfasst von: Andreas Malcher

Erschienen in: Natural Computing | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Iterative arrays with restricted internal inter-cell communication are investigated. A quantitative measure for the communication is defined by counting the number of uses of the links between cells and it is differentiated between the sum of all communications of an accepting computation and the maximum number of communications per cell occurring in accepting computations. The computational complexity of both classes of devices is investigated and put into relation. In addition, a strict hierarchy depending on the maximum number of communications per cell is established. Furthermore, it is shown that almost all commonly studied decidability questions are not semidecidable for iterative arrays with restricted communication. Finally, non-recursive trade-offs are proved among the iterative arrays providing the strict hierarchy depending on the maximum number of communications per cell.

Vorheriger Artikel Universal logic elements constructed on the Turing Tumble

Nächster Artikel Joint optimization of the high-end equipment development task process and resource allocation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Chang JH, Ibarra OH, Palis MA (1987) Parallel parsing on a one-way array of finite-state machines. IEEE Trans Comput C–36:64–75CrossRef

Choffrut C, Culik K II (1984) On real-time cellular automata and trellis automata. Acta Inform 21:393–407MathSciNetCrossRef

Cole SN (1969) Real-time computation by \(n\)-dimensional iterative arrays of finite-state machines. IEEE Trans Comput C–18(4):349–365MathSciNetCrossRef

Fischer PC (1965) Generation of primes by a one-dimensional real-time iterative array. J ACM 12:388–394MathSciNetCrossRef

Holzer M, Kutrib M (2010) Descriptional complexity—an introductory survey. In: Martín-Vide C (ed) Scientific applications of language methods. Imperial College Press, London, pp 1–58MATH

Ibarra OH, Palis MA (1985) Some results concerning linear iterative (systolic) arrays. J Parallel Distrib Comput 2:182–218CrossRef

Ibarra OH, Palis MA (1988) Two-dimensional iterative arrays: characterizations and applications. Theor Comput Sci 57:47–86MathSciNetCrossRef

Kutrib M (2008) Cellular automata—a computational point of view. In: Bel-Enguix G, Jiménez-López MD, Martín-Vide C (eds) New developments in formal languages and applications, chapter 6. Springer, Berlin, pp 183–227CrossRef

Kutrib M (2009) Cellular automata and language theory. In: Meyers RA (ed) Encyclopedia of complexity and systems science. Springer, Berlin, pp 800–823CrossRef

Kutrib M, Malcher A (2009) Computations and decidability of iterative arrays with restricted communication. Parallel Process Lett 19(2):247–264MathSciNetCrossRef

Kutrib M, Malcher A (2009) On one-way one-bit \({O}(1)\)-message cellular automata. Electron Notes Theor Comput Sci 252:77–91MathSciNetCrossRef

Kutrib M, Malcher A (2010) Cellular automata with sparse communication. Theor Comput Sci 411(38–39):3516–3526MathSciNetCrossRef

Kutrib M, Malcher A (2010) One-way cellular automata, bounded languages, and minimal communication. J Autom Lang Comb 15(1/2):135–153MathSciNetMATH

Kutrib M, Malcher A (2011) Cellular automata with limited inter-cell bandwidth. Theor Comput Sci 412(30):3917–3931MathSciNetCrossRef

Kutrib M, Malcher A (2018) Cellular automata: descriptional complexity and decidability. In: Adamatzky A (ed) Reversibility and universality, emergence, complexity and computation, vol 30. Springer, Berlin, pp 129–168CrossRef

Malcher A (2004) On the descriptional complexity of iterative arrays. IEICE Trans Inf Syst E87–D:721–725

Mazoyer J, Terrier V (1999) Signals in one-dimensional cellular automata. Theor Comput Sci 217(1):53–80MathSciNetCrossRef

Smith AR III (1972) Real-time language recognition by one-dimensional cellular automata. J Comput Syst Sci 6(3):233–253MathSciNetCrossRef

Umeo H, Kamikawa N (2002) A design of real-time non-regular sequence generation algorithms and their implementations on cellular automata with 1-bit inter-cell communications. Fundam Inform 52:257–275MathSciNetMATH

Umeo H, Kamikawa N (2003) Real-time generation of primes by a 1-bit-communication cellular automaton. Fundam Inform 58:421–435MathSciNetMATH

Worsch T (2000) Linear time language recognition on cellular automata with restricted communication. In: Gonnet GH, Panario D, Viola A (eds) Theoretical informatics (LATIN 2000), LNCS, vol 1776. Springer, Berlin, pp 417–426CrossRef

Titel: Hierarchies and undecidability results for iterative arrays with sparse communication
verfasst von: Andreas Malcher
Publikationsdatum: 25.11.2019
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 4/2020
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09773-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

A survey on traffic optimization problem using biologically inspired techniques

Universal logic elements constructed on the Turing Tumble

The role of tessellation intersection in staggered quantum walks

Ensemble particle swarm optimization and differential evolution with alternative mutation method

Preface

Glider automorphisms and a finitary Ryan’s theorem for transitive subshifts of finite type

Premium Partner