Bis 1996 unter dem Titel: Bericht / Arbeitsgruppe Informatik

Recent Submissions

  • 18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008 

    Holzer, Markus; Kutrib, Martin; Malcher, Andreas (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 ...
  • Descriptional complexity of pushdown store languages 

    Malcher, Andreas; Meckel, Katja; Mereghetti, Carlo; Palano, Beatrice (2012)
    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 ...
  • On the complexity of rolling block and Alice mazes 

    Holzer, Markus; Jakobi, Sebastian (2012)
    We investigate the computational complexity of two maze problems, namely rolling block and Alice mazes. Simply speaking, in the former game one has to roll blocks through a maze, ending in a particular game situation, and ...
  • Simplifying regular expressions : A quantitative perspective 

    Gruber, Hermann; Gulan, Stefan (2009)
    In this work, we consider the efficient simplification of regular expressions. We suggest a quantitative comparison of heuristics for simplifying regular expressions. We propose a new normal form for regular expressions, ...
  • Cellular automata with sparse communication 

    Kutrib, Martin; Malcher, Andreas (2009)
    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 ...
  • Grid graphs with diagonal edges and the complexity of Xmas mazes 

    Holzer, Markus; Jakobi, Sebastian (2012)
    We investigate the computational complexity of some maze problems, namely the reachability problem for (undirected) grid graphs with diagonal edges, and the solvability of Xmas tree mazes. Simply speaking, in the latter ...
  • Tight bounds on the descriptional complexity of regular expressions 

    Gruber, Hermann; Holzer, Markus (2009)
    We improve on some recent results on lower bounds for conversion problems for regular expressions. In particular we consider the conversion of planar deterministic finite automata to regular expressions, study the effect ...
  • Below linear-time : Dimensions versus time 

    Kutrib, Martin (2000)
    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 ...
  • Efficient universal pushdown cellular automata and their application to complexity 

    Kutrib, Martin (2000)
    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. ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • Fault tolerant parallel pattern recognition 

    Kutrib, Martin; Löwe, Jan-Thomas (2000)
    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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...

View more