Efficient universal pushdown cellular automata and their application to complexity

dc.contributor.authorKutrib, Martin
dc.date.accessioned2022-09-12T09:38:48Z
dc.date.available2001-02-07T23:00:00Z
dc.date.available2022-09-12T09:38:48Z
dc.date.issued2000
dc.description.abstractIn order to obtain universal classical cellular automata an infinite space is required. Therefore, the number of required processors depends on the length of input data and, additionally, may increase during the computation. On the other hand, Turing machines are universal devices which have one processor only and additionally an infinite storage tape. Here an in some sense intermediate model is studied. The pushdown cellular automata are a stack augmented generalization of classical cellular automata. They form a massively parallel universal model where the number of processors is bounded by the length of input data. Effcient universal pushdown cellular automata and their efficiently verifiable encodings are proposed. They are applied to computational complexity, and tight time and stack-space hierarchies are shown. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-6104
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7575
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-7009
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 0004 / 2000
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectuniversal pushdown cellular automatade_DE
dc.subject.ddcddc:004de_DE
dc.titleEfficient universal pushdown cellular automata and their application to complexityen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id610
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
IfigReport0004.pdf
Größe:
321.59 KB
Format:
Adobe Portable Document Format