A new and systematic approach to machine vision-based robot manipulation of deformable (non-rigid) linear objects is introduced. This approach reduces the computational needs by using a simple state-oriented model of the objects. These states describe the relation of the object with respect to an obstacle and are derived from the object image and its features. Therefore, the object is segmented from a standard video frame using a fast segmentation algorithm. Several object features are presented which allow the state recognition of the object while being manipulated by the robot.

Self-adaptation allows software systems to autonomously adjust their behavior during run-time by handling all possible operating states that violate the requirements of the managed system. This requires an adaptation engine that receives adaptation requests during the monitoring process of the managed system and responds with an automated and appropriate adaptation response. During the last decade, several engineering methods have been introduced to enable self-adaptation in software systems. However, these methods lack addressing (1) run-time uncertainty that hinders the adaptation process and (2) the performance impacts resulted from the complexity and the large number of the adaptation space. This paper presents CRATER, a framework that builds an external adaptation engine for self-adaptive software systems. The adaptation engine, which is built on Case-based Reasoning, handles the aforementioned challenges together. This paper is braced with an experiment illustrating the benefits of this framework. The experimental results shows the potential of CRATER in terms handling run-time uncertainty and adaptation remembrance that enhances the performance for large number of adaptation space.

Abstract Nowadays, people and systems created by people are generating an unprecedented amount of data. This data has brought us data-driven services with a variety of applications that affect people’s behavior. One of these applications is the emergent online social networks as a method for communicating with each other, getting and sharing information, looking for jobs, and many other things. However, the tremendous growth of these online social networks has also led to many new challenges that need to be addressed. In this context, the goal of this thesis is to better understand the dynamics between the members of online social networks from two perspectives. The first perspective is to better understand the process and the motives underlying link formation in online social networks. We utilize external information to predict whether two members of an online social network are friends or not. Also, we contribute a framework for assessing the strength of friendship ties. The second perspective is to better understand the decay dynamics of online social networks resulting from the inactivity of their members. Hence, we contribute a model, methods, and frameworks for understanding the decay mechanics among the members, for predicting members’ inactivity, and for understanding and analyzing inactivity cascades occurring during the decay. The results of this thesis are: (1) The link formation process is at least partly driven by interactions among members that take place outside the social network itself; (2) external interactions might help reduce the noise in social networks and for ranking the strength of the ties in these networks; (3) inactivity dynamics can be modeled, predicted, and controlled using the models contributed in this thesis, which are based on network measures. The contributions and the results of this thesis can be beneficial in many respects. For example, improving the quality of a social network by introducing new meaningful links and removing noisy ones help to improve the quality of the services provided by the social network, which, e.g., enables better friend recommendations and helps to eliminate fake accounts. Moreover, understanding the decay processes involved in the interaction among the members of a social network can help to prolong the engagement of these members. This is useful in designing more resilient social networks and can assist in finding influential members whose inactivity may trigger an inactivity cascade resulting in a potential decay of a network.

Typically software engineers implement their software according to the design of the software structure. Relations between classes and interfaces such as method-call relations and inheritance relations are essential parts of a software structure. Accordingly, analyzing several types of relations will benefit the static analysis process of the software structure. The tasks of this analysis include but not limited to: understanding of (legacy) software, checking guidelines, improving product lines, finding structure, or re-engineering of existing software. Graphs with multi-type edges are possible representation for these relations considering them as edges, while nodes represent classes and interfaces of software. Then, this multiple type edges graph can be mapped to visualizations. However, the visualizations should deal with the multiplicity of relations types and scalability, and they should enable the software engineers to recognize visual patterns at the same time. To advance the usage of visualizations for analyzing the static structure of software systems, I tracked difierent development phases of the interactive multi-matrix visualization (IMMV) showing an extended user study at the end. Visual structures were determined and classified systematically using IMMV compared to PNLV in the extended user study as four categories: High degree, Within-package edges, Cross-package edges, No edges. In addition to these structures that were found in these handy tools, other structures that look interesting for software engineers such as cycles and hierarchical structures need additional visualizations to display them and to investigate them. Therefore, an extended approach for graph layout was presented that improves the quality of the decomposition and the drawing of directed graphs according to their topology based on rigorous definitions. The extension involves describing and analyzing the algorithms for decomposition and drawing in detail giving polynomial time complexity and space complexity. Finally, I handled visualizing graphs with multi-type edges using small-multiples, where each tile is dedicated to one edge-type utilizing the topological graph layout to highlight non-trivial cycles, trees, and DAGs for showing and analyzing the static structure of software. Finally, I applied this approach to four software systems to show its usefulness.

Dealing with information in modern times involves users to cope with hundreds of thousands of documents, such as articles, emails, Web pages, or News feeds. Above all information sources, the World Wide Web presents information seekers with great challenges. It offers more text in natural language than one is capable to read. The key idea for this research intends to provide users with adaptable filtering techniques, supporting them in filtering out the specific information items they need. Its realization focuses on developing an Information Extraction system, which adapts to a domain of concern, by interpreting the contained formalized knowledge. Utilizing the Resource Description Framework (RDF), which is the Semantic Web's formal language for exchanging information, allows extending information extractors to incorporate the given domain knowledge. Because of this, formal information items from the RDF source can be recognized in the text. The application of RDF allows a further investigation of operations on recognized information items, such as disambiguating and rating the relevance of these. Switching between different RDF sources allows changing the application scope of the Information Extraction system from one domain of concern to another. An RDF-based Information Extraction system can be triggered to extract specific kinds of information entities by providing it with formal RDF queries in terms of the SPARQL query language. Representing extracted information in RDF extends the coverage of the Semantic Web's information degree and provides a formal view on a text from the perspective of the RDF source. In detail, this work presents the extension of existing Information Extraction approaches by incorporating the graph-based nature of RDF. Hereby, the pre-processing of RDF sources allows extracting statistical information models dedicated to support specific information extractors. These information extractors refine standard extraction tasks, such as the Named Entity Recognition, by using the information provided by the pre-processed models. The post-processing of extracted information items enables representing these results in RDF format or lists, which can now be ranked or filtered by relevance. Post-processing also comprises the enrichment of originating natural language text sources with extracted information items by using annotations in RDFa format. The results of this research extend the state-of-the-art of the Semantic Web. This work contributes approaches for computing customizable and adaptable RDF views on the natural language content of Web pages. Finally, due to the formal nature of RDF, machines can interpret these views allowing developers to process the contained information in a variety of applications.

This thesis presents a novel, generic framework for information segmentation in document images. A document image contains different types of information, for instance, text (machine printed/handwritten), graphics, signatures, and stamps. It is necessary to segment information in documents so that to process such segmented information only when required in automatic document processing workflows. The main contribution of this thesis is the conceptualization and implementation of an information segmentation framework that is based on part-based features. The generic nature of the presented framework makes it applicable to a variety of documents (technical drawings, magazines, administrative, scientific, and academic documents) digitized using different methods (scanners, RGB cameras, and hyper-spectral imaging (HSI) devices). A highlight of the presented framework is that it does not require large training sets, rather a few training samples (for instance, four pages) lead to high performance, i.e., better than previously existing methods. In addition, the presented framework is simple and can be adapted quickly to new problem domains. This thesis is divided into three major parts on the basis of document digitization method (scanned, hyper-spectral imaging, and camera captured) used. In the area of scanned document images, three specific contributions have been realized. The first of them is in the domain of signature segmentation in administrative documents. In some workflows, it is very important to check the document authenticity before processing the actual content. This can be done based on the available seal of authenticity, e.g., signatures. However, signature verification systems expect pre-segmented signature image, while signatures are usually a part of document. To use signature verification systems on document images, it is necessary to first segment signatures in documents. This thesis shows that the presented framework can be used to segment signatures in administrative documents. The system based on the presented framework is tested on a publicly available dataset where it outperforms the state-of-the-art methods and successfully segmented all signatures, while less than half of the found signatures are false positives. This shows that it can be applied for practical use. The second contribution in the area of scanned document images is segmentation of stamps in administrative documents. A stamp also serves as a seal for documents authenticity. However, the location of stamp on the document can be more arbitrary than a signature depending on the person sealing the document. This thesis shows that a system based on our generic framework is able to extract stamps of any arbitrary shape and color. The evaluation of the presented system on a publicly available dataset shows that it is also able to segment black stamps (that were not addressed in the past) with a recall and precision of 83% and 73%, respectively. %Furthermore, to segment colored stamps, this thesis presents a novel feature set which is based on intensity gradient, is able to extract unseen, colored, arbitrary shaped, textual as well as graphical stamps, and outperforms the state-of-the-art methods. The third contribution in the scanned document images is in the domain of information segmentation in technical drawings (architectural floorplans, maps, circuit diagrams, etc.) containing usually a large amount of graphics and comparatively less textual components. Further, as in technical drawings, text is overlapping with graphics. Thus, automatic analysis of technical drawings uses text/graphics segmentation as a pre-processing step. This thesis presents a method based on our generic information segmentation framework that is able to detect the text, which is touching graphical components in architectural floorplans and maps. Evaluation of the method on a publicly available dataset of architectural floorplans shows that it is able to extract almost all touching text components with precision and recall of 71% and 95%, respectively. This means that almost all of the touching text components are successfully extracted. In the area of hyper-spectral document images, two contributions have been realized. Unlike normal three channels RGB images, hyper-spectral images usually have multiple channels that range from ultraviolet to infrared regions including the visible region. First, this thesis presents a novel automatic method for signature segmentation from hyper-spectral document images (240 spectral bands between 400 - 900 nm). The presented method is based on a part-based key point detection technique, which does not use any structural information, but relies only on the spectral response of the document regardless of ink color and intensity. The presented method is capable of segmenting (overlapping and non-overlapping) signatures from varying backgrounds like, printed text, tables, stamps, logos, etc. Importantly, the presented method can extract signature pixels and not just the bounding boxes. This is substantial when signatures are overlapping with text and/or other objects in image. Second, this thesis presents a new dataset comprising of 300 documents scanned using a high-resolution hyper-spectral scanner. Evaluation of the presented signature segmentation method on this hyper-spectral dataset shows that it is able to extract signature pixels with the precision and recall of 100% and 79%, respectively. Further contributions have been made in the area of camera captured document images. A major problem in the development of Optical Character Recognition (OCR) systems for camera captured document images is the lack of labeled camera captured document images datasets. In the first place, this thesis presents a novel, generic, method for automatic ground truth generation/labeling of document images. The presented method builds large-scale (i.e., millions of images) datasets of labeled camera captured / scanned documents without any human intervention. The method is generic and can be used for automatic ground truth generation of (scanned and/or camera captured) documents in any language, e.g., English, Russian, Arabic, Urdu. The evaluation of the presented method, on two different datasets in English and Russian, shows that 99.98% of the images are correctly labeled in every case. Another important contribution in the area of camera captured document images is the compilation of a large dataset comprising 1 million word images (10 million character images), captured in a real camera-based acquisition environment, along with the word and character level ground truth. The dataset can be used for training as well as testing of character recognition systems for camera-captured documents. Various benchmark tests are performed to analyze the behavior of different open source OCR systems on camera captured document images. Evaluation results show that the existing OCRs, which already get very high accuracies on scanned documents, fail on camera captured document images. Using the presented camera-captured dataset, a novel character recognition system is developed which is based on a variant of recurrent neural networks, i.e., Long Short Term Memory (LSTM) that outperforms all of the existing OCR engines on camera captured document images with an accuracy of more than 95%. Finally, this thesis provides details on various tasks that have been performed in the area closely related to information segmentation. This includes automatic analysis and sketch based retrieval of architectural floor plan images, a novel scheme for online signature verification, and a part-based approach for signature verification. With these contributions, it has been shown that part-based methods can be successfully applied to document image analysis.

Today, many publishers (e.g., websites, mobile application developers) commonly use third-party analytics services and social widgets. Unfortunately, this scheme allows these third parties to track individual users across the web, creating privacy concerns and leading to reactions to prevent tracking via blocking, legislation and standards. While improving user privacy, these efforts do not consider the functionality third-party tracking enables publishers to use: to obtain aggregate statistics about their users and increase their exposure to other users via online social networks. Simply preventing third-party tracking without replacing the functionality it provides cannot be a viable solution; leaving publishers without essential services will hurt the sustainability of the entire ecosystem. In this thesis, we present alternative approaches to bridge this gap between privacy for users and functionality for publishers and other entities. We first propose a general and interaction-based third-party cookie policy that prevents third-party tracking via cookies, yet enables social networking features for users when wanted, and does not interfere with non-tracking services for analytics and advertisements. We then present a system that enables publishers to obtain rich web analytics information (e.g., user demographics, other sites visited) without tracking the users across the web. While this system requires no new organizational players and is practical to deploy, it necessitates the publishers to pre-define answer values for the queries, which may not be feasible for many analytics scenarios (e.g., search phrases used, free-text photo labels). Our second system complements the first system by enabling publishers to discover previously unknown string values to be used as potential answers in a privacy-preserving fashion and with low computation overhead for clients as well as servers. These systems suggest that it is possible to provide non-tracking services with (at least) the same functionality as today’s tracking services.

The Context and Its Importance: In safety and reliability analysis, the information generated by Minimal Cut Set (MCS) analysis is large. The Top Level event (TLE) that is the root of the fault tree (FT) represents a hazardous state of the system being analyzed. MCS analysis helps in analyzing the fault tree (FT) qualitatively-and quantitatively when accompanied with quantitative measures. The information shows the bottlenecks in the fault tree design leading to identifying weaknesses of the system being examined. Safety analysis (containing the MCS analysis) is especially important for critical systems, where harm can be done to the environment or human causing injuries, or even death during the system usage. Minimal Cut Set (MCS) analysis is performed using computers and generating a lot of information. This phase is called MCS analysis I in this thesis. The information is then analyzed by the analysts to determine possible issues and to improve the design of the system regarding its safety as early as possible. This phase is called MCS analysis II in this thesis. The goal of my thesis was developing interactive visualizations to support MCS analysis II of one fault tree (FT). The Methodology: As safety visualization-in this thesis, Minimal Cut Set analysis II visualization-is an emerging field and no complete checklist regarding Minimal Cut Set analysis II requirements and gaps were available from the perspective of visualization and interaction capabilities, I have conducted multiple studies using different methods with different data sources (i.e., triangulation of methods and data) for determining these requirements and gaps before developing and evaluating visualizations and interactions supporting Minimal Cut Set analysis II. Thus, the following approach was taken in my thesis: 1- First, a triangulation of mixed methods and data sources was conducted. 2- Then, four novel interactive visualizations and one novel interaction widget were developed. 3- Finally, these interactive visualizations were evaluated both objectively and subjectively (compared to multiple safety tools) from the point of view of users and developers of the safety tools that perform MCS analysis I with respect to their degree in supporting MCS analysis II and from the point of non-domain people using empirical strategies. The Spiral tool supports analysts with different visions, i.e., full vision, color deficiency protanopia, deuteranopia, and tritanopia. It supports 100 out of 103 (97%) requirements obtained from the triangulation and it fills 37 out of 39 (95%) gaps. Its usability was rated high (better than their best currently used tools) by the users of the safety and reliability tools (RiskSpectrum, ESSaRel, FaultTree+, and a self-developed tool) and at least similar to the best currently used tools from the point of view of the CAFTA tool developers. Its quality was higher regarding its degree of supporting MCS analysis II compared to the FaultTree+ tool. The time spent for discovering the critical MCSs from a problem size of 540 MCSs (with a worst case of all equal order) was less than a minute while achieving 99.5% accuracy. The scalability of the Spiral visualization was above 4000 MCSs for a comparison task. The Dynamic Slider reduces the interaction movements up to 85.71% of the previous sliders and solves the overlapping thumb issues by the sliders provides the 3D model view of the system being analyzed provides the ability to change the coloring of MCSs according to the color vision of the user provides selecting a BE (i.e., multi-selection of MCSs), thus, can observe the BEs' NoO and provides its quality provides two interaction speeds for panning and zooming in the MCS, BE, and model views provide a MCS, a BE, and a physical tab for supporting the analysis starting by the MCSs, the BEs, or the physical parts. It combines MCS analysis results and the model of an embedded system enabling the analysts to directly relate safety information with the corresponding parts of the system being analyzed and provides an interactive mapping between the textual information of the BEs and MCSs and the parts related to the BEs. Verifications and Assessments: I have evaluated all visualizations and the interaction widget both objectively and subjectively, and finally evaluated the final Spiral visualization tool also both objectively and subjectively regarding its perceived quality and regarding its degree of supporting MCS analysis II.

Information Visualization (InfoVis) and Human-Computer Interaction (HCI) have strong ties with each other. Visualization supports the human cognitive system by providing interactive and meaningful images of the underlying data. On the other side, the HCI domain cares about the usability of the designed visualization from the human perspectives. Thus, designing a visualization system requires considering many factors in order to achieve the desired functionality and the system usability. Achieving these goals will help these people in understanding the inside behavior of complex data sets in less time. Graphs are widely used data structures to represent the relations between the data elements in complex applications. Due to the diversity of this data type, graphs have been applied in numerous information visualization applications (e.g., state transition diagrams, social networks, etc.). Therefore, many graph layout algorithms have been proposed in the literature to help in visualizing this rich data type. Some of these algorithms are used to visualize large graphs, while others handle the medium sized graphs. Regardless of the graph size, the resulting layout should be understandable from the users’ perspective and at the same time it should fulfill a list of aesthetic criteria to increase the representation readability. Respecting these two principles leads to produce a resulting graph visualization that helps the users in understanding and exploring the complex behavior of critical systems. In this thesis, we utilize the graph visualization techniques in modeling the structural and behavioral aspects of embedded systems. Furthermore, we focus on evaluating the resulting representations from the users’ perspectives. The core contribution of this thesis is a framework, called ESSAVis (Embedded Systems Safety Aspect Visualizer). This framework visualizes not only some of the safety aspects (e.g. CFT models) of embedded systems, but also helps the engineers and experts in analyzing the system safety critical situations. For this, the framework provides a 2Dplus3D environment in which the 2D represents the graph representation of the abstract data about the safety aspects of the underlying embedded system while the 3D represents the underlying system 3D model. Both views are integrated smoothly together in the 3D world fashion. In order to check the effectiveness and feasibility of the framework and its sub-components, we conducted many studies with real end users as well as with general users. Results of the main study that targeted the overall ESSAVis framework show high acceptance ratio and higher accuracy with better performance using the provided visual support of the framework. The ESSAVis framework has been designed to be compatible with different 3D technologies. This enabled us to use the 3D stereoscopic depth of such technologies to encode nodes attributes in node-link diagrams. In this regard, we conducted an evaluation study to measure the usability of the stereoscopic depth cue approach, called the stereoscopic highlighting technique, against other selected visual cues (i.e., color, shape, and sizes). Based on the results, the thesis proposes the Reflection Layer extension to the stereoscopic highlighting technique, which was also evaluated from the users’ perspectives. Additionally, we present a new technique, called ExpanD (Expand in Depth), that utilizes the depth cue to show the structural relations between different levels of details in node-link diagrams. Results of this part opens a promising direction of the research in which visualization designers can get benefits from the richness of the 3D technologies in visualizing abstract data in the information visualization domain. Finally, this thesis proposes the application of the ESSAVis frame- work as a visual tool in the educational training process of engineers for understanding the complex concepts. In this regard, we conducted an evaluation study with computer engineering students in which we used the visual representations produced by ESSAVis to teach the principle of the fault detection and the failure scenarios in embedded systems. Our work opens the directions to investigate many challenges about the design of visualization for educational purposes.

We present two techniques for reasoning from cases to solve classification tasks: Induction and case-based reasoning. We contrast the two technologies (that are often confused) and show how they complement each other. Based on this, we describe how they are integrated in one single platform for reasoning from cases: The Inreca system.

MOLTKE is a research project dealing with a complex technical application. After describing the domain of CNCmachining centers and the applied KA methods, we summarize the concrete KA problems which we have to handle. Then we describe a KA mechanism which supports an engineer in developing a diagnosis system. In chapter 6 weintroduce learning techniques operating on diagnostic cases and domain knowledge for improving the diagnostic procedure of MOLTKE. In the last section of this chapter we outline some essential aspects of organizationalknowledge which is heavily applied by engineers for analysing such technical systems (Qualitative Engineering). Finally we give a short overview of the actual state of realization and our future plans.

We present an approach to systematically describing case-based reasoning systems bydifferent kinds of criteria. One main requirement was the practical relevance of these criteria and their usability for real-life applications. We report on the results we achieved from a case study carried out in the INRECA1 Esprit project.

Im Bereich der Expertensysteme ist das Problemlösen auf der Basis von Fallbeispielen ein derzeit sehr aktuelles Thema. Da sich sehr unterschiedliche Fachgebiete und Disziplinen hiermit auseinandersetzen, existiert allerdings eine entsprechende Vielfalt an Begriffen und Sichten auf fallbasiertes Problemlösen. In diesem Beitrag werden wir einige für das fallbasierte Problemlösen wichtige Begriffe präzisieren bzw. begriffliche Zusammenhänge aufdecken. Die dabei verfolgte Leitlinie ist weniger die, ein vollständiges Begriffsgebäude zu entwickeln, sondern einen ersten Schritt in Richtung eines einfachen Beschreibungsrahmens zu gehen, um damit den Vergleich verschiedener Ansätze und Systeme zu ermöglichen. Auf dieser Basis wird dann der derzeitige Stand der Forschung am Beispiel konkreter Systeme zur fallbasierten Diagnose dargelegt. Den Abschluss bildet eine Darstellung bislang offener Fragen und interessanter Forschungsziele.

Retrieval of cases is one important step within the case-based reasoning paradigm. We propose an improvement of this stage in the process model for finding most similar cases with an average effort of O[log2n], n number of cases. The basic idea of the algorithm is to use the heterogeneity of the search space for a density-based structuring and to employ this precomputed structure, a k-d tree, for efficient case retrieval according to a given similarity measure sim. In addition to illustrating the basic idea, we present the expe- rimental results of a comparison of four different k-d tree generating strategies as well as introduce the notion of virtual bounds as a new one that significantly reduces the retrieval effort from a more pragmatic perspective. The presented approach is fully implemented within the (Patdex) system, a case-based reasoning system for diagnostic applications in engineering domains.

We propose an integrated approach to decision support and diagnostic problems based on top-down induction of decision trees (TDIDT) and case-based reasoning (CBR).

A prime motivation for using XML to directly represent pieces of information is the ability of supporting ad-hoc or 'schema-later' settings. In such scenarios, modeling data under loose data constraints is essential. Of course, the flexibility of XML comes at a price: the absence of a rigid, regular, and homogeneous structure makes many aspects of data management more challenging. Such malleable data formats can also lead to severe information quality problems, because the risk of storing inconsistent and incorrect data is greatly increased. A prominent example of such problems is the appearance of the so-called fuzzy duplicates, i.e., multiple and non-identical representations of a real-world entity. Similarity joins correlating XML document fragments that are similar can be used as core operators to support the identification of fuzzy duplicates. However, similarity assessment is especially difficult on XML datasets because structure, besides textual information, may exhibit variations in document fragments representing the same real-world entity. Moreover, similarity computation is substantially more expensive for tree-structured objects and, thus, is a serious performance concern. This thesis describes the design and implementation of an effective, flexible, and high-performance XML-based similarity join framework. As main contributions, we present novel structure-conscious similarity functions for XML trees - either considering XML structure in isolation or combined with textual information -, mechanisms to support the selection of relevant information from XML trees and organization of this information into a suitable format for similarity calculation, and efficient algorithms for large-scale identification of similar, set-represented objects. Finally, we validate the applicability of our techniques by integrating our framework into a native XML database management system; in this context we address several issues around the integration of similarity operations into traditional database architectures.

When designing autonomous mobile robotic systems, there usually is a trade-off between the three opposing goals of safety, low-cost and performance. If one of these design goals is approached further, it usually leads to a recession of one or even both of the other goals. If for example the performance of a mobile robot is increased by making use of higher vehicle speeds, then the safety of the system is usually decreased, as, under the same circumstances, faster robots are often also more dangerous robots. This decrease of safety can be mitigated by installing better sensors on the robot, which ensure the safety of the system, even at high speeds. However, this solution is accompanied by an increase of system cost. In parallel to mobile robotics, there is a growing amount of ambient and aware technology installations in today's environments - no matter whether in private homes, offices or factory environments. Part of this technology are sensors that are suitable to assess the state of an environment. For example, motion detectors that are used to automate lighting can be used to detect the presence of people. This work constitutes a meeting point between the two fields of robotics and aware environment research. It shows how data from aware environments can be used to approach the abovementioned goal of establishing safe, performant and additionally low-cost robotic systems. Sensor data from aware technology, which is often unreliable due to its low-cost nature, is fed to probabilistic methods for estimating the environment's state. Together with models, these methods cope with the uncertainty and unreliability associated with the sensor data, gathered from an aware environment. The estimated state includes positions of people in the environment and is used as an input to the local and global path planners of a mobile robot, enabling safe, cost-efficient and performant mobile robot navigation during local obstacle avoidance as well as on a global scale, when planning paths between different locations. The probabilistic algorithms enable graceful degradation of the whole system. Even if, in the extreme case, all aware technology fails, the robots will continue to operate, by sacrificing performance while maintaining safety. All the presented methods of this work have been validated using simulation experiments as well as using experiments with real hardware.

Distributed systems are an alternative to shared-memorymultiprocessors for the execution of parallel applications.PANDA is a runtime system which provides architecturalsupport for efficient parallel and distributed program-ming. PANDA supplies means for fast user-level threads,and for a transparent and coordinated sharing of objectsacross a homogeneous network. The paper motivates themajor architectural choices that guided our design. Theproblem of sharing data in a distributed environment isdiscussed, and the performance of appropriate mecha-nisms provided by the PANDA prototype implementation isassessed.

This paper introduces a new high Level programming language for a novel class of computational devices namely data-procedural machines. These machines are by up to several orders of magnitude more efficient than the von Neumann paradigm of computers and are as flexible and as universal as computers. Their efficiency and flexibility is achieved by using field-programmable logic as the essential technology platform. The paper briefly summarizes and illustrates the essential new features of this language by means of two example programs.

This paper presents a new kind of abstraction, which has been developed for the purpose of proofplanning. The basic idea of this paper is to abstract a given theorem and to find an abstractproof of it. Once an abstract proof has been found, this proof has to be refined to a real proofof the original theorem. We present a goal oriented abstraction for the purpose of equality proofplanning, which is parameterized by common parts of the left- and right-hand sides of the givenequality. Therefore, this abstraction technique provides an abstract equality problem which ismore adequate than those generated by the abstractions known so far. The presented abstractionalso supports the heuristic search process based on the difference reduction paradigm. We give aformal definition of the abstract space including the objects and their manipulation. Furthermore,we prove some properties in order to allow an efficient implementation of the presented abstraction.

In this paper we show that distributing the theorem proving task to several experts is a promising idea. We describe the team work method which allows the experts to compete for a while and then to cooperate. In the cooperation phase the best results derived in the competition phase are collected and the less important results are forgotten. We describe some useful experts and explain in detail how they work together. We establish fairness criteria and so prove the distributed system to be both, complete and correct. We have implementedour system and show by non-trivial examples that drastical time speed-ups are possible for a cooperating team of experts compared to the time needed by the best expert in the team.

We study deterministic conditional rewrite systems, i.e. conditional rewrite systemswhere the extra variables are not totally free but 'input bounded'. If such a systemR is quasi-reductive then !R is decidable and terminating. We develop a critical paircriterion to prove confluence if R is quasi-reductive and strongly deterministic. In thiscase we prove that R is logical, i.e./!R==R holds. We apply our results to proveHorn clause programs to be uniquely terminating.This research was supported by the Deutsche Forschungsgemeinschaft, SFB 314, Project D4

In this paper we are interested in an algebraic specification language that (1) allowsfor sufficient expessiveness, (2) admits a well-defined semantics, and (3) allows for formalproofs. To that end we study clausal specifications over built-in algebras. To keep thingssimple, we consider built-in algebras only that are given as the initial model of a Hornclause specification. On top of this Horn clause specification new operators are (partially)defined by positive/negative conditional equations. In the first part of the paper wedefine three types of semantics for such a hierarchical specification: model-theoretic,operational, and rewrite-based semantics. We show that all these semantics coincide,provided some restrictions are met. We associate a distinguished algebra A spec to ahierachical specification spec. This algebra is initial in the class of all models of spec.In the second part of the paper we study how to prove a theorem (a clause) valid in thedistinguished algebra A spec . We first present an abstract framework for inductive theoremprovers. Then we instantiate this framework for proving inductive validity. Finally wegive some examples to show how concrete proofs are carried out.This report was supported by the Deutsche Forschungsgemeinschaft, SFB 314 (D4-Projekt)

This paper discusses the benefits and drawbacks of caching and replication strategies in the WWW with respect to the Internet infrastructure. Bandwidth consumption, latency, and overall error rates are considered to be most important from a network point of view. The dependencies of these values with input parameters like degree of replication, document popularity, actual cache hit rates, and error rates are highlighted. In order to determine the influence of different caching and replication strategies on the behavior of a single proxy server with respect to these values, trace-based simulations are used. Since the overall effects of such strate- gies can hardly be decided with this approach alone, a mathematical model has been developed to deal with their influence on the network as a whole. Together, this two-tiered approach permits us to propose quantita- tive assessments on the influence different caching and replication proposals (are going to) have on the Inter- net infrastructure.

As global networks are being used by more and more people,they are becoming increasingly interesting for commercial appli-cations. The recent success and change in direction of the World-Wide Web is a clear indication for this. However, this success meta largely unprepared communications infrastructure. The Inter-net as an originally non-profit network did neither offer the secu-rity, nor the globally available accounting infrastructure byitself.These problems were addressed in the recent past, but in aseemingly ad-hoc manner. Several different accounting schemessensible for only certain types of commercial transactions havebeen developed, which either seem to neglect the problems ofscalability, or trade security for efficiency. Finally, some propos-als aim at achieving near perfect security at the expense of effi-ciency, thus rendering those systems to be of no practical use.In contrast, this paper presents a suitably configurable schemefor accounting in a general, widely distributed client/server envi-ronment. When developing the protocol presented in this paper,special attention has been paid to make this approach work wellin the future setting of high-bandwidth, high-latency internets.The developed protocol has been applied to a large-scale distrib-uted application, a WWW-based software development environ-ment.