Bericht / Arbeitsgruppe Informatikhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22072023-12-01T10:02:15Z2023-12-01T10:02:15ZOn the power of one-way bounded cellular time computersBuchholz, ThomasKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22162022-07-04T09:38:27Z1996-01-01T00:00:00ZOn the power of one-way bounded cellular time computers
Buchholz, Thomas; Kutrib, Martin
Comparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to timeconstruct and timecompute functions. Timeconstruction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas timecomputation requires the distinguished cell to enter a distinguished state firstly at time step f(n), where n is the length of the input. Here the family of functions which are timeconstructible by a twoway unbounded cellular space (F(CS)) is characterized in terms of functions which are timecomputable by one of the simplest cellular devices, a oneway bounded cellular automaton (C (OCA)). Conceptually, timeconstructible functions have to be strictly increasing. Regarding that restriction the reverse characterization is shown, too. Some results concerning the structure of F(CS) and C(OCA) and their relation to formal language recognition are established.
1996-01-01T00:00:00ZInformatik an der JLUG : "Interdiziplinärer Workshop"Kröger, HennerKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22142022-07-04T09:38:32Z1996-01-01T00:00:00ZInformatik an der JLUG : "Interdiziplinärer Workshop"
Kröger, Henner; Kutrib, Martin
1996-01-01T00:00:00ZSome relations between massively parallel arraysBuchholz, ThomasKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22152022-07-04T09:38:31Z1996-01-01T00:00:00ZSome relations between massively parallel arrays
Buchholz, Thomas; Kutrib, Martin
Relations between various models for massively parallel computers are investigated. These are arrays of finitestate machines -- eventually augmented by pushdown storage -- operating synchronously. The architectures differ mainly in how the input is supplied and how the single nodes are interconnected. The comparisons are made in terms of their capabilities to timeconstruct and timecompute functions. That means given an constant input of length n a distinguished cell has to enter distinguished states after f(1); : : : ; f(n) respectively f(n) time steps.
1996-01-01T00:00:00ZOn time computability of functions in one-way cellular automataBuchholz, ThomasKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22122022-07-04T09:38:39Z1995-01-01T00:00:00ZOn time computability of functions in one-way cellular automata
Buchholz, Thomas; Kutrib, Martin
The capability of oneway (spacebounded) cellular automata (OCA) to timecompute functions is investigated. That means given an constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C (OCA)) is characterized in terms of formal language recognition. Several functions are proved to be timecomputable and properties of C(OCA) are given. The timecomputation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.
1995-01-01T00:00:00Z5. Theorietag : "Automaten und Formale Sprachen" : Schloss Rauischholzhausen, 28./29.09.1995https://jlupub.ub.uni-giessen.de//handle/jlupub/22132022-07-04T09:39:55Z1995-01-01T00:00:00Z5. Theorietag : "Automaten und Formale Sprachen" : Schloss Rauischholzhausen, 28./29.09.1995
Kutrib, Martin; Worsch, Thomas
1995-01-01T00:00:00ZParallele AutomatenKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22102022-07-04T09:38:47Z1994-01-01T00:00:00ZParallele Automaten
Kutrib, Martin
1994-01-01T00:00:00ZOn stack-augmented polyautomataKutrib, Martinhttps://jlupub.ub.uni-giessen.de//handle/jlupub/22112022-07-04T09:40:03Z1995-01-01T00:00:00ZOn stack-augmented polyautomata
Kutrib, Martin
A stack augmented generalization of cellular automata, the pushdown cellular automata, are investigated. We are studying the language accepting capabilities of such devices. Closure properties of realtime, lineartime and unrestricted time language families are shown. The relationships of these families with each other and to languages of sequential automata are considered.
1995-01-01T00:00:00Z