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.

A geometrical heuristic for drawing concept lattices

Concept lattices are used in formal concept analysis to represent data conceptually so that the original data are still recognizable. Their line diagrams should reflect the semantical relationships within the data. Up to now, no satisfactory automatic drawing programs for this task exist. The geometrical heuristic is the most successful tool for drawing concept lattices manually. It ueses a geometric representation as intermediate step between the list of upper covers and the line diagram of the lattice.

Virtual Radio Engine

Software Defined Radio (SDR) hardware platforms use parallel architectures. Current concepts of developing applications (such as WLAN) for these platforms are complex, because developers describe an application with hardware-specifics that are relevant to parallelism such as mapping and scheduling. To reduce this complexity, we have developed a new programming approach for SDR applications, called Virtual Radio Engine (VRE). VRE defines a language for describing applications, and a tool chain that consists of a compiler kernel and other tools (such as a code generator) to generate executables. The thesis presents this concept, as well as describes the language and the compiler kernel that have been developed by the author. The language is hardware-independent, i.e., developers describe tasks and dependencies between them. The compiler kernel performs automatic parallelization, i.e., it is capable of transforming a hardware-independent program into a hardware-specific program by solving hardware-specifics, in particular mapping, scheduling and synchronizations. Thus, VRE simplifies programming tasks as developers do not solve hardware-specifics manually.

Attribute exploration with background implications and exceptions

Implications between attributes can represent knowledge about objects in a specified context. This knowledge representation is especially useful when it is not possible to list all specified objects. Attribute exploration is a tool of formal concept analysis that supports the acquisition of this knowledge. For a specified context this interactive procedure determines a miminal list of valid implications between attributes of this context together with a list of objects which are counterexamples for all implications not valid in the context. This paper describes how the exploration can be modified such that it determines a mimimal set of implications that fills the gap between previously given implications (called background implications) and all valid implications. The list of implications can be simplified further if exceptions are allowed for the implications.

Exploration tools in formal concept analysis

The development of conceptual knowledge systems specifically requests knowledge acquisition tools within the framework of formal concept analysis. In this paper, the existing tools are presented, and furhter developments are discussed.

Concept exploration - a tool for creating and exploring conceptual hierarchies

Concept exploration is a knowledge acquisition tool for interactively exploring the hierarchical structure of finitely generated lattices. Applications comprise the support of knowledge engineers by constructing a type lattice for conceptual graphs, and the exploration of large formal contexts in formal concept analysis.

Hierarchies of conceptual scales

Formal Concept Analysis allows to derive conceptual hierarchies from data tables. Formal Concept Analysis is applied in various domains, e.g., data analysis, information retrieval, and knowledge discovery in databases. In order to deal with increasing sizes of the data tables (and to allow more complex data structures than just binary attributes), conceputal scales habe been developed. They are considered as metadata which structure the data conceptually. But in large applications, the number of conceptual scales increases as well. Techniques are needed which support the navigation of the user also on this meta-level of conceptual scales. In this paper, we attack this problem by extending the set of scales by hierarchically ordered higher level scales and by introducing a visualization technique called nested scaling. We extend the two-level architecture of Formal Concept Analysis (the data table plus one level of conceptual scales) to many-level architecture with a cascading system of conceptual scales. The approach also allows to use representation techniques of Formal Concept Analysis for the visualization of thesauri and ontologies.

Conceptual knowledge discovery with frequent concept lattices

Knowledge discovery support environments include beside classical data analysis tools also data mining tools. For supporting both kinds of tools, a unified knowledge representation is needed. We show that concept lattices which are used as knowledge representation in Conceptual Information Systems can also be used for structuring the results of mining association rules. Vice versa, we use ideas of association rules for reducing the complexity of the visualization of Conceptual Information Systems.