One guess one-way cellular arrays

dc.contributor.author	Buchholz, Thomas
dc.contributor.author	Klein, Andreas
dc.contributor.author	Kutrib, Martin
dc.date.accessioned	2022-09-12T09:38:45Z
dc.date.available	1998-07-08T22:00:00Z
dc.date.available	2022-09-12T09:38:45Z
dc.date.issued	1998
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-269
dc.identifier.uri	https://jlupub.ub.uni-giessen.de//handle/jlupub/7564
dc.identifier.uri	http://dx.doi.org/10.22029/jlupub-6998
dc.description.abstract	Oneway cellular automata with restricted nondeterminism are investigated. The number of allowed nondeterministic state transitions is limited to a constant. It is shown that a limit to exactly one step does not decrease the language accepting capabilities. We prove a speedup result that allows any lineartime computation to be spedup to realtime. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the realtime languages.	en
dc.language.iso	en	de_DE
dc.relation.ispartofseries	IFIG Research Report; 9801 / 1998
dc.rights	In Copyright	*
dc.rights.uri	http://rightsstatements.org/page/InC/1.0/	*
dc.subject.ddc	ddc:004	de_DE
dc.title	One guess one-way cellular arrays	en
dc.type	workingPaper	de_DE
local.affiliation	FB 07 - Mathematik und Informatik, Physik, Geographie	de_DE
local.opus.id	26
local.opus.institute	Institut für Informatik	de_DE
local.opus.fachgebiet	Informatik	de_DE

Urheberrechtlich geschützt