CD-Systems of Restarting Automata

Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

Global Optimization Algorithms and their Application to Distributed Systems

In this report, we discuss the application of global optimization and Evolutionary Computation to distributed systems. We therefore selected and classified many publications, giving an insight into the wide variety of optimization problems which arise in distributed systems. Some interesting approaches from different areas will be discussed in greater detail with the use of illustrative examples.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

Applicability of Emergence Engineering to Distributed Systems Scenarios

Genetic Programming can be effectively used to create emergent behavior for a group of autonomous agents. In the process we call Offline Emergence Engineering, the behavior is at first bred in a Genetic Programming environment and then deployed to the agents in the real environment. In this article we shortly describe our approach, introduce an extended behavioral rule syntax, and discuss the impact of the expressiveness of the behavioral description to the generation success, using two scenarios in comparison: the election problem and the distributed critical section problem. We evaluate the results, formulating criteria for the applicability of our approach.

On-line analytical processing with conceptual information systems

A conceptual information system consists of a database together with conceptual hierarchies. The management system TOSCANA visualizes arbitrary combinations of conceptual hierarchies by nested line diagrams and allows an on-line interaction with a database to analyze data conceptually. The paper describes the conception of conceptual information systems and discusses the use of their visualization techniques for on-line analytical processing (OLAP).

Reuse in the development process of TOSCANA systems

TOSCANA is a graphical tool that supports the human-centered interactive processes of conceptual knowledge processing. The generality of the approach makes TOSCANA a universal tool applicable to a variety of domains. Only the so-called conceptual scales have to be designed for new applications. The presentation shows how the use of abstract scales allows the reuse of formerly defined conceptual scales. Furthermore it describes how thesauri and conceptual taxonomies can be integrated in the generation of conceptual scales.

Numerical aspects in the data model of conceptual information systems

While most data analysis and decision support tools use numerical aspects of the data, Conceptual Information Systems focus on their conceptual structure. This paper discusses how both approaches can be combined.

Acquiring expert knowledge for the design of conceptual information systems

Conceptual Information Systems unfold the conceptual structure of data stored in relational databases. In the design phase of the system, conceptual hierarchies have to be created which describe different aspects of the data. In this paper, we describe two principal ways of designing such conceptual hierarchies, data driven design and theory driven design and discuss advantages and drawbacks. The central part of the paper shows how Attribute Exploration, a knowledge acquisition tool developped by B. Ganter can be applied for narrowing the gap between both approaches.

Dual retrieval in conceptual information systems

Conceptual Information Systems provide a multi-dimensional conceptually structured view on data stored in relational databases. On restricting the expressiveness of the retrieval language, they allow the visualization of sets of realted queries in conceptual hierarchies, hence supporting the search of something one does not have a precise description, but only a vague idea of. Information Retrieval is considered as the process of finding specific objects (documents etc.) out of a large set of objects which fit to some description. In some data analysis and knowledge discovery applications, the dual task is of interest: The analyst needs to determine, for a subset of objects, a description for this subset. In this paper we discuss how Conceptual Information Systems can be extended to support also the second task.

Conceptual information systems discussed through an IT-security tool

Conceptual Information Systems are based on a formalization of the concept of "concept" as it is discussed in traditional philosophical logic. This formalization supports a human-centered approach to the development of Information Systems. We discuss this approach by means of an implemented Conceptual Information System for supporting IT security management in companies and organizations.

Reverse pivoting in conceptual information systems

In database marketing, the behavior of customers is analyzed by studying the transactions they have performed. In order to get a global picture of the behavior of a customer, his single transactions have to be composed together. In On-Line Analytical Processing, this operation is known as reverse pivoting. With the ongoing data analysis process, reverse pivoting has to be repeated several times, usually requiring an implementation in SQL. In this paper, we present a construction for conceptual scales for reverse pivoting in Conceptual Information Systems, and also discuss the visualization. The construction allows the reuse of previously created queries without reprogramming and offers a visualization of the results by line diagrams.

CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions

We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton.