Auflistung IFIG Research Report nach DDC-Klassifikation "ddc:004"
Anzeige der Dokumente 1-20 von 57
-
18. Theorietag "Automaten und Formale Sprachen" : Wettenberg-Launsbach bei Gießen 30. September - 2. Oktober 2008
(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 ... -
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 ... -
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 ... -
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 ... -
Cellular automata with sparse communication
(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 ... -
Comments on Monoids Induced by NFAs
(2023-03)We 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 ... -
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 ... -
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 ... -
Descriptional complexity of pushdown store languages
(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 ... -
Deterministic set automata
(2014)We 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 ... -
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 ... -
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. ... -
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 ... -
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 ... -
Fast One-Way Cellular Automata
(2001) -
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 ...