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 Erscheinungsdatum

Zu einem Punkt im Index springen:
Gerade angezeigt 1 - 20 von 91
  • Vorschaubild
    Item
    Parallele Automaten
    (1994) Kutrib, Martin
  • Vorschaubild
    Item
    On time computability of functions in one-way cellular automata
    (1995) Buchholz, Thomas; Kutrib, Martin
    The capability of one­way (space­bounded) cellular automata (OCA) to time­compute functions is investigated. That means given an constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C (OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time­computable and properties of C(OCA) are given. The time­computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.
  • Vorschaubild
    Item
    On stack-augmented polyautomata
    (1995) Kutrib, Martin
    A stack augmented generalization of cellular automata, the pushdown cellular automata, are investigated. We are studying the language accepting capabilities of such devices. Closure properties of real­time, linear­time and unrestricted time language families are shown. The relationships of these families with each other and to languages of sequential automata are considered.
  • Vorschaubild
    Item
  • Vorschaubild
    Item
    Informatik an der JLUG : "Interdiziplinärer Workshop"
    (1996) Kröger, Henner; Kutrib, Martin
  • Vorschaubild
    Item
    On the power of one-way bounded cellular time computers
    (1996) Buchholz, Thomas; Kutrib, Martin
    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
    Some relations between massively parallel arrays
    (1996) Buchholz, Thomas; Kutrib, Martin
    Relations between various models for massively parallel computers are investigated. These are arrays of finite­state machines -- eventually augmented by pushdown storage -- operating synchronously. The architectures differ mainly in how the input is supplied and how the single nodes are interconnected. The comparisons are made in terms of their capabilities to time­construct and time­compute functions. That means given an constant input of length n a distinguished cell has to enter distinguished states after f(1); : : : ; f(n) respectively f(n) time steps.
  • 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
    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
    Probalistic and truth-functional many-valued logic programming
    (1998) Lukasiewicz, Thomas
    We introduce probabilistic many­valued logic programs in which the implication connective is interpreted as material implication. We show that probabilistic many-valued logic programming is computationally more complex than classical logic programming. More precisely, some deduction problems that are P­complete for classical logic programs are shown to be co­NP­complete for probabilistic many­valued logic programs. We then focus on many­valued logic programming in Pr*n as an approximation of probabilistic many­valued logic programming. Surprisingly, many­valued logic programs in Pr*n have both a probabilistic semantics in probabilities over a set of possible worlds and a truth­functional semantics in the finite­valued Lukasiewicz logics Ln. Moreover, many­valued logic programming in Pr*n has a model and fixpoint characterization, a proof theory, and computational properties that are very similar to those of classical logic programming. We especially introduce the proof theory of many­valued logic programming in Pr*n and show its soundness and completeness.
  • Vorschaubild
    Item
    Heterogeneous active agents
    (1998) Eiter, Thomas; Subrahmanian, V.S; Pick, George
    Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called Agent Programs using which, the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent Programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs, and study the computation price to be paid (in terms of complexity) for such epistemic desiderata. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning. Last, but not least, we have built a simulation of a Supply Chain application in terms of our theory, building on top of commercial software systems such as Microsoft Access and ESRI's MapObject.
  • Vorschaubild
    Item
    On interacting automata with limited nondeterminism
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    One­way and two­way 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 real­time, linear­time and unrestricted­time computations. A speed­up result that allows any linear­time computation to be sped­up to real­time 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.
  • 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
    On time reduction and simulation in cellular spaces
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    We 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.
  • Vorschaubild
    Item
    One guess one-way cellular arrays
    (1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    One­way 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 speed­up result that allows any linear­time computation to be sped­up to real­time. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the real­time languages.
  • Vorschaubild
    Item
    Räumliche Konzentration der Verpackungsmaschinenbau-Industrie in Mittelhessen : Eine Analyse des Gründungsgeschehens
    (1998) Mossig, Ivo
    Stellt man die Standorte der Verpackungsmaschinenbau-Betriebe in Deutschland1 dar, so fällt auf, daß sich die Betriebe nicht gleichmäßig verteilen, sondern auf wenige Schwerpunktregionen konzentrieren (vgl. Abb. 1). Die bedeutendste Agglomeration mit den meisten Betrieben findet sich nordöstlich von Stuttgart im Rems-Murr-Kreis mit der Kreisstadt Waiblingen und im Landkreis Schwäbisch-Hall. Die Region um Gießen2 bildet mit einer Vielzahl kleiner Betriebe die zweitwichtigste Konzentration des deutschen Verpackungsmaschinenbaus.Das Ziel des vorliegenden Beitrags besteht darin zu erklären, warum es zu einer derartigen räumlichen Konzentration von Industriebetrieben der gleichen Branche gekommen ist. Da das räumliche Verteilungsbild das Ergebnis unternehmerischer Standortentscheidungen ist, stellt sich hierbei die Frage nach den Motiven und Gründen der Standortwahl. Eine mögliche Erklärung für die räumliche Konzentration der Verpackungsmaschinenbau-Betriebe stellen lokale Spin-off-Gründungen dar. Deshalb soll das Gründungsgeschehen insbesondere unter dem Aspekt der Spin-off-Gründungen analysiert werden.
  • 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
    Preferred answer sets for extended logic programs
    (1998) Brewka, Gerd; Eiter, Thomas
    In this paper, we address the issue of how Gelfond and Lifschitz's answer set semantics for extended logic programs can be suitably modified to handle prioritized programs. In such programs an ordering on the program rules is used to express preferences. We show how this ordering can be used to define preferred answer sets and thus to increase the set of consequences of a program. We define a strong and a weak notion of preferred answer sets. The first takes preferences more seriously, while the second guarantees the existence of a preferred answer set for programs possessing at least one answer set. Adding priorities to rules is not new, and has been explored in different contexts. However, we show that many approaches to priority handling, most of which are inherited from closely related formalisms like default logic, are not suitable and fail on intuitive examples. Our approach, which obeys abstract, general principles that any approach to prioritized knowledge representation should satisfy, handles them in the expected way. Moreover, we investigate the complexity of our approach. It appears that strong preference on answer sets does not add on the complexity of the principal reasoning tasks, and weak preference leads only to a mild increase in complexity.
  • Vorschaubild
    Item
    On tally languages and generalized interacting automata
    (1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
    Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well­known result that each tally language acceptable by a classical one­way cellular automaton (OCA) in real­time 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 non­regular 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.