Now showing items 1-20 of 56

    • Existential second-order logic over strings 

      Eiter, Thomas; Gottlob, Georg; Gurevich, Yuri (1997)
      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 ...
    • Enhancing symbolic model checking by AI techniques 

      Buccafurri, Francesco; Eiter, Thomas; Gottlob, Georg; Leone, Nicola (1997)
      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 ...
    • Decision lists and related Boolean functions 

      Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa (1998)
      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 ...
    • On interacting automata with limited nondeterminism 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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. ...
    • Probalistic and truth-functional many-valued logic programming 

      Lukasiewicz, Thomas (1998)
      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 ...
    • Computing intersections of Horn theories for reasoning with models 

      Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa (1998)
      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 ...
    • On time reduction and simulation in cellular spaces 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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 ...
    • One guess one-way cellular arrays 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1998)
      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 ...
    • A first-order representation of stable models 

      Eiter, Thomas; Lu, James; Subrahmanian, V.S (1998)
      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 ...
    • Heterogeneous active agents 

      Eiter, Thomas; Subrahmanian, V.S; Pick, George (1998)
      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 ...
    • Preferred answer sets for extended logic programs 

      Brewka, Gerd; Eiter, Thomas (1998)
      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 ...
    • On tally languages and generalized interacting automata 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      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 ...
    • Iterative arrays with small time bounds 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      An 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 ...
    • Real-time language recognition by alternating cellular automata 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      The capabilities of alternating cellular automata (ACA) to accept formal languages are investigated. Several notions of alternation in cellular automata have been proposed. Here we study so­called nonuniform ACAs. Our ...
    • Automata arrays and context-free languages 

      Kutrib, Martin (1999)
      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 ...
    • Probalistic logic programming under maximum entropy 

      Lukasiewicz, Thomas; Kern-Isberner, Gabriele (1999)
      In this paper, we focus on the combination of probabilistic logic programming with the principle of maximum entropy. We start by defining probabilistic queries to probabilistic logic programs and their answer substitutions ...
    • Iterative arrays with limited nondeterministic communication cell 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      Iterative 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 ...
    • Iterative arrays with a wee bit alternation 

      Buchholz, Thomas; Klein, Andreas; Kutrib, Martin (1999)
      An 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 ...
    • Massively parallel pattern recognition with link failures 

      Löwe, Jan-Thomas; Kutrib, Martin (2000)
      The capabilities of reliable computations in linear cellular arrays with communication failures are investigated in terms of pattern recognition. The defective processing elements (cells) that cause the misoperations are ...
    • Deterministic Turing machines in the range between real-time and linear-time 

      Klein, Andreas; Kutrib, Martin (2000)
      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 ...