Anzeige der Dokumente 1-11 von 11

    • Iterative arrays with a wee bit alternation 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • Iterative arrays with limited nondeterministic communication cell 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • Iterative arrays with small time bounds 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • On interacting automata with limited nondeterminism 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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. ...
    • On tally languages and generalized interacting automata 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • On the power of one-way bounded cellular time computers 

      Buchholz, Thomas; Kutrib, Martin (1996)
      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 ...
    • On time computability of functions in one-way cellular automata 

      Buchholz, Thomas; Kutrib, Martin (1995)
      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 ...
    • On time reduction and simulation in cellular spaces 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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 ...
    • One guess one-way cellular arrays 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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 ...
    • Real-time language recognition by alternating cellular automata 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • Some relations between massively parallel arrays 

      Buchholz, Thomas; Kutrib, Martin (1996)
      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 ...