Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Natural Computing
Published in: Natural Computing 4/2020

25-11-2019

Hierarchies and undecidability results for iterative arrays with sparse communication

Author: Andreas Malcher

Published in: Natural Computing | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Universal logic elements constructed on the Turing Tumble
next article Joint optimization of the high-end equipment development task process and resource allocation

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
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
Cole SN (1969) Real-time computation by \(n\)-dimensional iterative arrays of finite-state machines. IEEE Trans Comput C–18(4):349–365MathSciNetCrossRef
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) 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
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
Metadata
Title
Hierarchies and undecidability results for iterative arrays with sparse communication
Author
Andreas Malcher
Publication date
25-11-2019
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 4/2020
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-019-09773-3

Other articles of this Issue 4/2020

Natural Computing 4/2020 Go to the issue

OriginalPaper

Sequentializing cellular automata

EditorialNotes

Preface

OriginalPaper

A binary monkey search algorithm variation for solving the set covering problem

OriginalPaper

Optimal shape design of an autonomous underwater vehicle based on multi-objective particle swarm optimization

OriginalPaper

A new multi-stage perturbed differential evolution with multi-parameter adaption and directional difference

OriginalPaper

Joint optimization of the high-end equipment development task process and resource allocation

Premium Partner

    Image Credits