IFIG Research Report
Dauerhafte URI für die Sammlung
Stöbern nach
Auflistung IFIG Research Report nach Autor:in "Klein, Andreas"
Gerade angezeigt 1 - 13 von 13
Treffer pro Seite
Sortieroptionen
Item A Time Hierarchy for Bounded One-Way Cellular Automata(2001) Klein, Andreas; Kutrib, MartinItem Deterministic Turing machines in the range between real-time and linear-time(2000) Klein, Andreas; Kutrib, MartinDeterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n + r(n) where r E o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. For these classes weak closure properties are proved. Finally, it is shown that similar results are valid for several types of acceptors with the same time bounds. CR Subject Classification (1998): F.1.3, F.1.1, F.4.3Item Fast One-Way Cellular Automata(2001) Klein, Andreas; Kutrib, MartinItem Grammars with Scattered Nonterminals(2002) Klein, Andreas; Kutrib, MartinItem Iterative arrays with a wee bit alternation(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinAn 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 realtime 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.Item Iterative arrays with limited nondeterministic communication cell(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinIterative 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 realtime language families. Finally we prove several closure properties of these families.Item Iterative arrays with small time bounds(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinAn 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.Item On interacting automata with limited nondeterminism(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinOneway and twoway 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 realtime, lineartime and unrestrictedtime computations. A speedup result that allows any lineartime computation to be spedup to realtime 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.Item On tally languages and generalized interacting automata(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinDevices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the wellknown result that each tally language acceptable by a classical oneway cellular automaton (OCA) in realtime 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 nonregular 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.Item On time reduction and simulation in cellular spaces(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinWe 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.Item One guess one-way cellular arrays(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinOneway 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.Item Real-time language recognition by alternating cellular automata(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, MartinThe 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 socalled nonuniform ACAs. Our considerations center on space bounded realtime computations. In particular, we prove that there is no difference in acceptance power regardless whether oneway or twoway communication lines are provided. Moreover, the relations between realtime ACAs and deterministic (CA) and nondeterministic (NCA) cellular automata are investigated. It is proved that even the realtime ACAs gain exponential speedup against nondeterministic NCAs. Comparing ACAs with deterministic CAs it is shown that realtime ACAs are strictly more powerful than realtime CAs.Item Self-Assembling Finite Automata(2002) Klein, Andreas; Kutrib, Martin