Browsing FB 07  Mathematik und Informatik, Physik, Geographie by DDCClassification "ddc:004"
Now showing items 120 of 63

18. Theorietag "Automaten und Formale Sprachen" : WettenbergLaunsbach 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 firstorder 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 contextfree 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 selfreproduction. From a computer scientific point of view they are a model for ... 
Below lineartime : Dimensions versus time
(2000)Deterministic ddimensional 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 intercell 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 ... 
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 realtime and lineartime
(2000)Deterministic ktape and multitape Turing machines with oneway, twoway 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 secondorder 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 OneWay Cellular Automata
(2001) 
Fault tolerant parallel pattern recognition
(2000)The general capabilities of fault tolerant computations in oneway and twoway linear cellular arrays are investigated in terms of pattern recognition. The defective processing elements (cells) that cause the misoperations ...