FB 07 - Mathematik und Informatik, Physik, Geographie

Dauerhafte URI für den Bereich

jlupub.ub.uni-giessen.de/handle/jlupub/1037

Stöbern nach

Auflistung FB 07 - Mathematik und Informatik, Physik, Geographie nach Autor:in "Buchholz, Thomas"

Gerade angezeigt 1 - 11 von 11
  • Vorschaubild
    Item
    Iterative arrays with a wee bit alternation
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    An iterative array is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. We are investigating iterative arrays with an alternating communication cell. All the other automata are deterministic. The number of alternating state transitions is regarded as a limited resource which depends on the length of the input. We center our attention to real­time computations and compare alternating IAs with nondeterministic IAs. By proving that the language families of the latter are not closed under complement for sublogarithmic limits it is shown that alternation is strictly more powerful than nondeterminism. Moreover, for these limits there exist infinite hierarchies of properly included alternating language families. It is shown that these families are closed under boolean operations.
  • Vorschaubild
    Item
    Iterative arrays with limited nondeterministic communication cell
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    Iterative arrays with restricted nondeterminism are investigated. Non-determinism is provided for the distinguished communication cell only. All the other cells are deterministic ones. Moreover, the number of allowed nondeterministic state transitions is limited dependent on the length of the input. It is shown that the limit can be reduced by a constant factor without affecting the language accepting capabilities, but for sublogarithmic limits there exists a infinite hierarchy of properly included real­time language families. Finally we prove several closure properties of these families.
  • Vorschaubild
    Item
    Iterative arrays with small time bounds
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    An iterative arrays is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. Sometimes in the literature this model is referred to as cellular automaton with sequential input mode. We investigate deterministic iterative arrays (IA) with small time bounds between real-time and linear-time. It is shown that there exists an infinite dense hierarchy of strictly included complexity classes in that range. The result closes the last gap in the time hierarchy of IAs.
  • Vorschaubild
    Item
    On interacting automata with limited nondeterminism
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    One­way and two­way cellular language acceptors with restricted non­ determinism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real­time, linear­time and unrestricted­time computations. A speed­up result that allows any linear­time computation to be sped­up to real­time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and [Epsilon]­free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.
  • Vorschaubild
    Item
    On tally languages and generalized interacting automata
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well­known result that each tally language acceptable by a classical one­way cellular automaton (OCA) in real­time has to be a regular language we will answer the three natural questions 'How much time do we have to provide?' 'How much power do we have to plug in the single cells (i.e., how complex has a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept non­regular tally languages. We show the surprising result that for some classes of generalized interacting automata parallelism does not lead to more accepting power than obtained by a single sequential cell. Adding a wee bit of nondeterminism an infinite hierarchy of unary language families can be shown by allowing more and more nondeterminism.
  • 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
    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
    On time reduction and simulation in cellular spaces
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    We prove a generalized and corrected version of the time reduction theorem for cellular spaces. One basic tool for investigations in this field is the concept of simulation between systems of automata. We propose a general formal definition of the intuitive concept and relate it to the notions which appear in the literature.
  • Vorschaubild
    Item
    One guess one-way cellular arrays
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    One­way 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 speed­up result that allows any linear­time computation to be sped­up to real­time. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the real­time languages.
  • Vorschaubild
    Item
    Real-time language recognition by alternating cellular automata
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    The capabilities of alternating cellular automata (ACA) to accept formal languages are investigated. Several notions of alternation in cellular automata have been proposed. Here we study so­called nonuniform ACAs. Our considerations center on space bounded real­time computations. In particular, we prove that there is no difference in acceptance power regardless whether one­way or two­way communication lines are provided. Moreover, the relations between real­time ACAs and deterministic (CA) and nondeterministic (NCA) cellular automata are investigated. It is proved that even the real­time ACAs gain exponential speed­up against nondeterministic NCAs. Comparing ACAs with deterministic CAs it is shown that real­time ACAs are strictly more powerful than real­time CAs.
  • 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.