IFIG Research Report

Dauerhafte URI für die Sammlung

jlupub.ub.uni-giessen.de/handle/jlupub/7512
Bis 1996 unter dem Titel: Bericht / Arbeitsgruppe Informatik

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

Stöbern nach

Auflistung IFIG Research Report nach Auflistung nach Fachbereich/Einrichtung "FB 07 - Mathematik und Informatik, Physik, Geographie"

Gerade angezeigt 1 - 20 von 59
  • Vorschaubild
    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.
  • Vorschaubild
    Item
    A first-order representation of stable models
    (1998) Eiter, Thomas; Lu, James; Subrahmanian, V.S
    Turi (1991) introduced the important notion of a constrained atom: an atom with associated equality and disequality constraints on its arguments. A set of constrained atoms is a constrained interpretation. We investigate how non­ground representations of both the stable model semantics and the well­founded semantics may be obtained through Turi's approach. The practical implication of this is that the well­founded model (or the set of stable models) may be partially pre­computed at compile­time, resulting in the association of each predicate symbol in the program to a constrained atom. Algorithms to create such models are presented, both for the well founded case, and the case of stable models. Query processing reduces to checking whether each atom in the query is true in a stable model (resp. well­founded model). This amounts to showing the atom is an instance of one of some constrained atom whose associated constraint is solvable. Various related complexity results are explored, and the impacts of these results are discussed from the point of view of implementing systems that incorporate the stable and well­founded semantics.
  • Vorschaubild
    Item
    A Short Comment on Controlled Context-Free Grammar Derivations
    (2024-07-04) Holzer, Markus
    We prove that the family of languages generated by regularly controlled grammars with control languages accepted by ordered automata is equal to the family of languages generated by matrix grammars. To our knowledge, this equivalence has been overlooked in the literature.
  • Vorschaubild
    Item
    A Time Hierarchy for Bounded One-Way Cellular Automata
    (2001) Klein, Andreas; Kutrib, Martin
  • Vorschaubild
    Item
  • Vorschaubild
    Item
    Automata arrays and context-free languages
    (1999) Kutrib, Martin
    From 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.1
  • Vorschaubild
    Item
    Below linear-time : Dimensions versus time
    (2000) Kutrib, Martin
    Deterministic 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.3
  • Vorschaubild
    Item
    Cellular automata with sparse communication
    (2009) Kutrib, Martin; Malcher, Andreas
    We 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)].
  • Vorschaubild
    Item
    Comments on Monoids Induced by NFAs
    (2023-03) Holzer, Markus
    We summarize known results on the transformation monoid of nondeterministic finite automata (NFAs) from semigroup theory. In particular, we list what is known from the literature on the size of monoids induced by NFAs and their (minimal) number of generators - a comprehensive list of these generators is given in the Appendix. It is shown that any language accepted by an n-state NFA has a syntactic monoid of size at most 2^{n^2}. This bound is reachable by the generators of the semigroup B_n of n x n Boolean matrices with the usual matrix multiplication except that we assume 1 + 1 = 1. The number of these generators grows exponentially in n. This is a significant difference to the deterministic case, where three generators suffice to generate all elements of T_n. Moreover, we prove a lower bound for the \nfa-to-\dfa\ conversion using Lambert's W function.
  • Vorschaubild
    Item
    Computing intersections of Horn theories for reasoning with models
    (1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa
    Model­based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models; in particular, we study taking their logical intersection. We present low­order polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection \Sigma of Horn theories \Sigma 1 ; : : : ; \Sigma l, represented by their characteristic models, can be found in linear time, and that some characteristic model of \Sigma can be found in polynomial time. Moreover, we present an algorithm which enumerates the models of \Sigma with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from \Sigma is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider an extension of Horn theories, and prove negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate.
  • Vorschaubild
    Item
    Decision lists and related Boolean functions
    (1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa
    We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1­decision lists has interesting relationships to independently defined classes such as disguised Horn functions, readonce functions, nested differences of concepts, threshold functions, and 2­monotonic functions. In particular, 1­decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1­decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.
  • Vorschaubild
    Item
    Descriptional complexity of pushdown store languages
    (2012) Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice
    It is well known that the pushdown store language P(M) of a pushdown automaton (PDA) M i.e., the language consisting of words occurring on the pushdownalong accepting computations of M is a regular language. Here, we design succinct nondeterministic finite automata (NFA) accepting P(M). In detail, an upper bound on the size of an NFA for P(M) is obtained, which is quadratic in the number of states and linear in the number of pushdown symbols of M. Moreover, this upper bound is shown to be asymptotically optimal. Then, several restricted variants of PDA are considered, leading to improved constructions. In all cases, we prove the asymptotical optimality of the size of the resulting NFA. Finally, we apply our results to decidability questions related to PDA, and obtain solutions in deterministic polynomial time.
  • Vorschaubild
    Item
    Deterministic set automata
    (2014) Kutrib, Martin; Malcher, Andreas; Wendlandt, Matthias
    We 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.
  • Vorschaubild
    Item
    Deterministic Turing machines in the range between real-time and linear-time
    (2000) Klein, Andreas; Kutrib, Martin
    Deterministic 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.3
  • Vorschaubild
    Item
    Economy of Description for Basic Constructions on Rational Transductions
    (2002) Bordihn, Henning; Holzer, Markus; Kutrib, Martin
  • Vorschaubild
    Item
    Efficient universal pushdown cellular automata and their application to complexity
    (2000) Kutrib, Martin
    In 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.1
  • Vorschaubild
    Item
    Enhancing symbolic model checking by AI techniques
    (1997) Buccafurri, Francesco; Eiter, Thomas; Gottlob, Georg; Leone, Nicola
    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
    Existential second-order logic over strings
    (1997) Eiter, Thomas; Gottlob, Georg; Gurevich, Yuri
    Existential second­order logic (ESO) and monadic second­order logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over word structures than MSO. However, little was known about the relationship between MSO and syntactic fragments of ESO. We shed light on this issue by completely characterizing this relationship for the prefix classes of ESO over strings, (i.e., finite word structures). Moreover, we determine the complexity of model checking over strings, for all ESO­prefix classes. Let ESO(Q) denote the prefix class containing all sentences of the shape 9RQ' where R is a list of predicate variables, Q is a first­order quantifier prefix from the prefix set Q, and ' is quantifier free. We show that ESO(9 \Lambda 89 \Lambda ) and ESO(9 \Lambda 88) are the maximal standard ESO­prefix classes contained in MSO, thus expressing only regular languages. We further prove the following dichotomy theorem: An ESO prefix­class either expresses only regular languages (and is thus in MSO), or it expresses some NP­complete languages. We also give a precise characterization of those ESO­prefix classes which are equivalent to MSO over strings, and of the ESO­prefix classes which are closed under complementation on strings.
  • Vorschaubild
    Item
    Fast One-Way Cellular Automata
    (2001) Klein, Andreas; Kutrib, Martin
  • Vorschaubild
    Item
    Fault tolerant parallel pattern recognition
    (2000) Kutrib, Martin; Löwe, Jan-Thomas
    The 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.4