IFIG Research Report
Dauerhafte URI für die Sammlung
Stöbern nach
Auflistung IFIG Research Report nach Autor:in "Kutrib, Martin"
Gerade angezeigt 1 - 20 von 34
Treffer pro Seite
Sortieroptionen
Item 18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008(2008)Der Theorietag ist die Jahrestagung der Fachgruppe Automaten und Formale Sprachen der Gesellschaft für Informatik. Er wird seit 1991 von Mitgliedern der Fachgruppe an wechselnden Orten in Deutschland und Österreich veranstaltet. Im Laufe des Theorietags findet auch die jährliche Fachgruppensitzung statt. Seit 1996 wird der Theorietag von einem eintägigen Workshop mit eingeladenen Vorträgen begleitet. Die bisherigen Austragungsorte waren Magdeburg (1991), Kiel (1992), Dagstuhl (1993), Herrsching (1994), Schloß Rauischholzhausen (1995), Cunnersdorf (1996), Barnstorf (1997), Riveris (1998), Schauenburg-Elmshagen (1999), Wien (2000), Wendgräben (2001), Wittenberg (2002), Herrsching (2003), Caputh (2004),Lauterbad (2005), Wien (2006) und Leipzig (2007). Der diesjährige Theorietag wird nach 13 Jahren wieder vom Institut für Informatik der Justus-Liebig-Universität Gießen ausgerichtet. Er findet mit dem vorangestellten Workshop über Selected Topics in Theoretical Computer Science vom 30. September bis zum 2. Oktober 2008 in Wettenberg-Launsbach bei Gießen statt. Teilnehmer aus Belgien, Deutschland, England, Frankreich, Italien, Österreich, Tschechien und Ungarn folgten der Einladung nach Mittelhessen.Item A Time Hierarchy for Bounded One-Way Cellular Automata(2001) Klein, Andreas; Kutrib, MartinItem Automata 2013 : exploratory papers ; 19th International Workshop on Cellular Automata and Discrete Complex Systems, Giessen, Germany, Sept. 17-19, 2013(2013) Kari, Jarkko; Kutrib, Martin; Malcher, Andreas (Hrsg.)Item Automata arrays and context-free languages(1999) Kutrib, MartinFrom a biological point of view automata arrays have been employed by John von Neumann in order to solve the logical problem of nontrivial self-reproduction. From a computer scientific point of view they are a model for massively parallel computing systems. Here we are dealing with automata arrays as acceptors for formal languages. Our focus of investigations concerns their capabilities to accept the classical linguistic languages. While there are simple relations to the regular and context-sensitive ones here we shed some light on the relations to the context-free languages and some of their important subfamilies. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1Item Below linear-time : Dimensions versus time(2000) Kutrib, MartinDeterministic d-dimensional Turing machines are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form id + r where r E o(id) is a sublinear function. It is shown that for any dimension d >= 1 there exist infinite time hierarchies of separated complexity classes in that range. Moreover, for the corresponding time bounds separated dimension hierarchies are proved. CR Subject Classification (1998): F.1.3, F.1.1, F.4.3Item Cellular automata with sparse communication(2009) Kutrib, Martin; Malcher, AndreasWe investigate cellular automata whose internal inter-cell communication is bounded. The communication is quantitatively measured by the number of uses of the links between cells. Bounds on the sum of all communications of a computation as well as bounds on the maximal number of communications that may appear between each two cells are considered. It is shown that even the weakest non-trivial device in question, that is,one-way cellular automata where each two neighboring cells may communicate constantly often only, accept rather complicated languages. We investigate the computational capacity of the devices in question and prove an infinite strict hierarchy depending on the bound on the total number of communications during a computation. Despite their sparse communication even for the weakest devices, by reduction of Hilbert´s tenth problem undecidability of several problems is derived. Finally, the question whether a given real-time one-way cellular automaton belongs to the weakest class is shown to be undecidable. This result can be adapted to answer an open question posed in [Vollmar, R.: Zur Zustandsänderungskomplexität von Zellularautomaten. In: Beiträge zur Theorie der Polyautomaten zweite Folge,Braunschweig (1982) 139 151 (in German)].Item Deterministic set automata(2014) Kutrib, Martin; Malcher, Andreas; Wendlandt, MatthiasWe consider the model of deterministic set automata which are basically deterministic finite automata equipped with a set as an additional storage medium. The basic operations on the set are the insertion of elements, the removing of elements, and the test whether or not an element is in the set. We investigate the computational power of deterministic set automata and compare the language class accepted with the context-free languages and classes of languages accepted by queue automata. As results the incomparability to all classes considered is obtained. In the second part of the paper, we examine the closure properties of the class of DSA languages under Boolean operations. Finally, we show that deterministic set automata may be an interesting model from a practical point of view by proving that their emptiness problem is decidable.Item 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 Economy of Description for Basic Constructions on Rational Transductions(2002) Bordihn, Henning; Holzer, Markus; Kutrib, MartinItem Efficient universal pushdown cellular automata and their application to complexity(2000) Kutrib, MartinIn order to obtain universal classical cellular automata an infinite space is required. Therefore, the number of required processors depends on the length of input data and, additionally, may increase during the computation. On the other hand, Turing machines are universal devices which have one processor only and additionally an infinite storage tape. Here an in some sense intermediate model is studied. The pushdown cellular automata are a stack augmented generalization of classical cellular automata. They form a massively parallel universal model where the number of processors is bounded by the length of input data. Effcient universal pushdown cellular automata and their efficiently verifiable encodings are proposed. They are applied to computational complexity, and tight time and stack-space hierarchies are shown. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1Item Fast One-Way Cellular Automata(2001) Klein, Andreas; Kutrib, MartinItem Fault tolerant parallel pattern recognition(2000) Kutrib, Martin; Löwe, Jan-ThomasThe general capabilities of fault tolerant computations in one-way and two-way linear cellular arrays are investigated in terms of pattern recognition. The defective processing elements (cells) that cause the misoperations are assumed to behave as follows. Dependent on the result of a self-diagnosis they store their working state locally such that it becomes visible to the neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. Arrays with static defects run the self-diagnosis once before the actual computation. Subsequently no more defects may occur.In case of dynamic defects cells may fail during the computation. We center our attention to patterns that are recognizable very fast, i.e. in real-time, but almost all results can be generalized to arbitrary recognition times in a straightforward manner. It is shown that fault tolerant recognition capabilities of two-way arrays with static defects are characterizable by intact one-way arrays and that one-way arrays are fault tolerant per se. For arrays with dynamic defects it is proved that the failures can be compensated as long as the number of adjacent defective cells is bounded. Arbitrary large defective regions (and thus fault tolerant computations) lead to a dramatically decrease of computing power. The recognizable patterns are those of a single processing element, the regular ones. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1, B.8.1, C.4Item Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k(2002) Holzer, Markus; Kutrib, MartinItem Flip-Pushdown Automata: Nondeterminism is Better Than Determinism(2003) Holzer, Markus; Kutrib, MartinItem Grammars with Scattered Nonterminals(2002) Klein, Andreas; Kutrib, MartinItem Improving Raster Image Run-Length Encoding Using Data Order(2001) Holzer, Markus; 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 Massively Parallel Fault Tolerant Computations on Syntactical Patterns(2001) Kutrib, Martin; Löwe, Jan-Thomas