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 Auflistung nach Fachbereich/Einrichtung "FB 07 - Mathematik und Informatik, Physik, Geographie"

Gerade angezeigt 1 - 20 von 91
  • 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
  • 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
  • Vorschaubild
    Item
    A Time Hierarchy for Bounded One-Way Cellular Automata
    (2001) Klein, Andreas; Kutrib, Martin
  • Vorschaubild
    Item
    Agrarstruktur in Ghandruk und Umgebung : Schwerpunkt Ackerbau und Hausgärten
    (2006) Bernardy, Katrin; Hofmann, Sabine
  • Vorschaubild
    Item
    Die Anbindung der Galerie Neustädter Tor an das Gießener Geschäftszentrum : Das Kopplungsverhalten von Kunden in der Gießener Innenstadt
    (2006) Dorenkamp, Ansgar
    Die Studie setzt sich mit der Fragestellung auseinander, inwiefern das Einkaufszentrum Galerie Neustädter Tor an das Gießener Geschäftszentrum im Seltersweg angebunden ist. Zu diesem Zweck wurden 671 Besucher des Selterswegs und der Galerie Neustädter Tor über ihr Einkaufsverhalten an beiden Standorten befragt. Dabei lag ein Fokus der Untersuchung darauf herauszubekommen, inwiefern die Kunden der Gießener Innenstadt bei ihren Einkäufen auf das Einzelhandelsangebot an beiden Standorten zurückgreifen. *Die Ergebnisse dieses Projekts zeigen, ob und inwiefern die Galerie Neustädter Tor und das Gießener Geschäftszentrum im Seltersweg aneinander angebunden sind und wie sich die Attraktivität Gießens als Einzelhandelsstandort mit der Eröffnung der Galerie Neustädter Tor aus der Sicht der Kunden verändert hat. Ebenso wird aus den Ergebnissen der Befragung deutlich, ob die Galerie Neustädter Tor Einfluss darauf hat, dass neue Kunden zum Einkaufen in die Gießener Innenstadt kommen.
  • Vorschaubild
    Item
  • Vorschaubild
    Item
  • 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
    Bevölkerung und Migration in Nepal und Ghandruk
    (2006) Hochstein, Marco; Schewe, Melanie
  • 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.