Bericht / Arbeitsgruppe Informatik

Dauerhafte URI für die Sammlung

jlupub.ub.uni-giessen.de/handle/jlupub/2207
Es stehen nur einzelne Bände der Schriftenreihe als PDF-Dokumente zur Verfügung. Bitte recherchieren Sie in unserem Katalog.
Ab 1997 unter dem Titel: IFIG Research Report

URN: urn:nbn:de:hebis:26-opus-29029

Suchen

Neueste Veröffentlichungen

Gerade angezeigt 1 - 7 von 7
  • Vorschaubild
    Item
    Some relations between massively parallel arrays
    (1996) Buchholz, Thomas; Kutrib, Martin
    Relations between various models for massively parallel computers are investigated. These are arrays of finite­state 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 time­construct and time­compute 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.
  • Vorschaubild
    Item
    Informatik an der JLUG : "Interdiziplinärer Workshop"
    (1996) Kröger, Henner; Kutrib, Martin
  • Vorschaubild
    Item
    On the power of one-way bounded cellular time computers
    (1996) 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 time­construct and time­compute functions. Time­construction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas time­computation 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 time­constructible by a two­way unbounded cellular space (F(CS)) is characterized in terms of functions which are time­computable by one of the simplest cellular devices, a one­way bounded cellular automaton (C (OCA)). Conceptually, time­constructible 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.
  • Vorschaubild
    Item
  • Vorschaubild
    Item
    On time computability of functions in one-way cellular automata
    (1995) Buchholz, Thomas; Kutrib, Martin
    The capability of one­way (space­bounded) cellular automata (OCA) to time­compute 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 time­computable and properties of C(OCA) are given. The time­computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.
  • Vorschaubild
    Item
    Parallele Automaten
    (1994) Kutrib, Martin
  • Vorschaubild
    Item
    On stack-augmented polyautomata
    (1995) 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 real­time, linear­time and unrestricted time language families are shown. The relationships of these families with each other and to languages of sequential automata are considered.