Liebe Nutzerinnen und Nutzer in der Zeit von Montag 22.04. 9:00Uhr bis voraussichtlich Mitwoch 24.04. 9:00Uhr ist JLUpub aufgrund von Wartungsarbeiten nicht erreichbar. Danke für Ihr Verständnis.
Dear users, JLUpub will be unavailable from Monday 22.04. 9:00 a.m. until probably Wednesday 24.04. 9:00 a.m. due to maintenance work. Thank you for your understanding.
FB 07 - Mathematik und Informatik, Physik, Geographie: Recent submissions
Anzeige der Dokumente 21-40 von 89
-
Grid graphs with diagonal edges and the complexity of Xmas mazes
(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 ... -
Massively parallel pattern recognition with link failures
(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 ... -
Below linear-time : Dimensions versus time
(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
(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. ... -
Deterministic Turing machines in the range between real-time and linear-time
(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
(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
(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 ... -
Automata arrays and context-free languages
(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 ... -
Decision lists and related Boolean functions
(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 1decision lists has interesting relationships to ... -
A first-order representation of stable models
(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 ... -
Preferred answer sets for extended logic programs
(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 ... -
Existential second-order logic over strings
(1997)Existential secondorder logic (ESO) and monadic secondorder 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
(1998)Modelbased 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 ... -
One guess one-way cellular arrays
(1998)Oneway 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 ... -
Heterogeneous active agents
(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 ... -
Enhancing symbolic model checking by AI techniques
(1997)Comparisons 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 ... -
On time reduction and simulation in cellular spaces
(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 ... -
Semi-Linear Lattices and Right One-Way Jumping Finite Automata
(2019)Right one-way jumping automata (ROWJFAs) are an automaton model that was recently introduced for processing the input in a discontinuous way. In [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. ... -
On interacting automata with limited nondeterminism
(1998)Oneway and twoway 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. ... -
Real-time language recognition by alternating cellular automata
(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 socalled nonuniform ACAs. Our ...