FB 07 - Mathematik und Informatik, Physik, Geographie
Dauerhafte URI für den Bereich
Stöbern nach
Auflistung FB 07 - Mathematik und Informatik, Physik, Geographie nach Auflistung nach Typ "workingPaper"
Gerade angezeigt 1 - 20 von 76
Treffer pro Seite
Sortieroptionen
Item A first-order representation of stable models(1998) Eiter, Thomas; Lu, James; Subrahmanian, V.STuri (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 nonground representations of both the stable model semantics and the wellfounded semantics may be obtained through Turi's approach. The practical implication of this is that the wellfounded model (or the set of stable models) may be partially precomputed at compiletime, 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. wellfounded 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 wellfounded semantics.Item A Short Comment on Controlled Context-Free Grammar Derivations(2024-07-04) Holzer, MarkusWe 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.Item A Time Hierarchy for Bounded One-Way Cellular Automata(2001) Klein, Andreas; Kutrib, MartinItem Die Anbindung der Galerie Neustädter Tor an das Gießener Geschäftszentrum : Das Kopplungsverhalten von Kunden in der Gießener Innenstadt(2006) Dorenkamp, AnsgarDie 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.Item Ausgewählte Aspekte zur sozialen Lage der Studierenden an der Justus-Liebig-Universität 2005(2005) Peighambari, Arman; Mossig, IvoItem 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 Comments on Monoids Induced by NFAs(2023-03) Holzer, MarkusWe 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.Item Computing intersections of Horn theories for reasoning with models(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, KazuhisaModelbased 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 loworder 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.Item Decision lists and related Boolean functions(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, KazuhisaWe 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 1decision lists has interesting relationships to independently defined classes such as disguised Horn functions, readonce functions, nested differences of concepts, threshold functions, and 2monotonic functions. In particular, 1decision 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 1decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.Item Descriptional complexity of pushdown store languages(2012) Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, BeatriceIt 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.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 Enhancing symbolic model checking by AI techniques(1997) Buccafurri, Francesco; Eiter, Thomas; Gottlob, Georg; Leone, NicolaComparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to timeconstruct and timecompute functions. Timeconstruction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas timecomputation 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 timeconstructible by a twoway unbounded cellular space (F(CS)) is characterized in terms of functions which are timecomputable by one of the simplest cellular devices, a oneway bounded cellular automaton (C (OCA)). Conceptually, timeconstructible 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.Item Evolutionary development of regional production clusters : A case study of the packaging machinery industry in Germany(2001) Mossig, IvoThe production of packaging machinery in Germany is only a small subsection of the mechanical engineering sector, with ca. 25000 employees in around 300 businesses. The factories are for the most part individual small- to medium-sized enterprises. Only 2.6% have more than 500 employees. More than half have fewer than 50 employees. In spite of the small size of the production units these businesses operate on a global scale. In 1997 78% of the machines were exported. Germany occupies the leading position in the world market with a market share of just under 30%. The production structures are oriented towards the demands of the customers and characterized by craftsmanship. Innovations are less the product of systematic research and development, but rather develop as a result of processes of adaptation to the requirements of the customers. As a whole the production of packaging machinery can be characterized as a ´low-tech´ branch of industry.