Show simple item record

dc.contributor.authorKutrib, Martin
dc.contributor.authorMalcher, Andreas
dc.date.accessioned2022-09-12T09:38:49Z
dc.date.available2012-11-23T09:53:19Z
dc.date.available2022-09-12T09:38:49Z
dc.date.issued2009
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-90815
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7578
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-7012
dc.description.abstractWe investigate cellular automata whose internal inter-cell communication is bounded. The communication is quantitatively measured by the number of uses of the links between cells. Bounds on the sum of all communications of a computation as well as bounds on the maximal number of communications that may appear between each two cells are considered. It is shown that even the weakest non-trivial device in question, that is,one-way cellular automata where each two neighboring cells may communicate constantly often only, accept rather complicated languages. We investigate the computational capacity of the devices in question and prove an infinite strict hierarchy depending on the bound on the total number of communications during a computation. Despite their sparse communication even for the weakest devices, by reduction of Hilbert´s tenth problem undecidability of several problems is derived. Finally, the question whether a given real-time one-way cellular automaton belongs to the weakest class is shown to be undecidable. This result can be adapted to answer an open question posed in [Vollmar, R.: Zur Zustandsänderungskomplexität von Zellularautomaten. In: Beiträge zur Theorie der Polyautomaten zweite Folge,Braunschweig (1982) 139 151 (in German)].de_DE
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 0903 / 2009
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleCellular automata with sparse communicationde_DE
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.id9081
local.opus.instituteInstitut für Informatikde_DE
local.opus.fachgebietInformatikde_DE


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

In Copyright