Technical Reports 2009

8 Publikation(en)

Flexible Workflows to Support Transactional Service Composition in Mobile Environments

Katharina Hahn, Heinz Schweppe


TR B-09-17

Service oriented computing provides suitable means to technically support distributed collaboration of heterogeneous devices, for example those present in mobile environments. E.g., many applications are built on composite Web-Services. However, when executing these applications in dynamic environments, failures of participating entities have to be optimistically coped with, in order to avoid inconsistent system states and thereby provide suitable correctness guarantees. Transactional coordination for services so far lacks the possibility to adapt failure handling to the current execution context, e.g. dynamically bound services at runtime. In this paper, we employ transactional service properties to ensure reliable, i.e., correct execution of workflows by still respecting the autonomy of participants. We propose algorithms to verifiy and alter the structure of the composition at runtime, thus adapting the control flow to the current execution context to ensure correct execution.

Polygonal Chains with pairwise identical Hausdorff Distance

Lutz Meißner

Takustraße 9, 14195 Berlin: Freie Universität Berlin, Institut für Informatik | 2009-07


The complexity of the Voronoi diagram for n polygonal chains and the Hausdorff distance is shown to be worst case 2n −1. Some bounds are given on the number of chains with limited size and fixed distance, and the relation between the sizes of two polygonal chains and their distance is examined.

Thema: Polygonal chains, Hausdorff distance, Voronoi Diagram, pairwise distances

General Game Playing mit stochastischen Spielen

Johannes Kulick, Marco Block, Raúl Rojas


In der Game Description Language lassen sich rundenbasierte Spiele mit vollständiger Information ohne stochastische Ereignisse beschreiben. Obwohl die Sprache erst 2005 entwickelt wurde, hat sie eine hohe Akzeptanz innerhalb derWissenschaftgemeinde. Es werden Programme entwickelt, die aus den Spielbeschreibungen Strategien ableiten und die Spiele erfolgreich spielen. In dieser Arbeit wird eine Erweiterung der Sprache GDL vorgestellt, mit der nun auch Spiele mit stochastischen Elementen beschrieben und gespielt werden können.

Haar-Based Features for High-Dimensional Images

The integral image approach allows the optimal computation of Haar-based features for real-time recognition of objects in image sequences. This short note gives a direction to generalize the approach to high-dimensional images.

Thema: Haar-Based Features, High-Dimensional Images

Realizing the Corporate Semantic Web: Concept Paper

Adrian Paschke, Gökhan Coskun, Marko Harasic, Ralf Heese, Markus Luczak-Rösch, Radoslaw Oldakowski, Ralph Schäfermeier, Olga Streibel

Takustr. 9, 14195 Berlin, Germany: Freie Universität Berlin, Institute of Computer Science | 2009-05-18

Realizing the Corporate Semantic Web: ...

In this concept paper, we outline our working plan for the next phase of the Corporate Semantic Web project. The plan covers the period from March 2009 to March 2010. Corporate ontology engineering will improve the facilitation of agile ontology engineering to lessen the costs of ontology development and, especially, maintenance. Corporate semantic collaboration focuses the human-centered aspects of knowledge management in corporate contexts. Corporate semantic search is settled on the highest application level of the three research areas and at that point it is a representative for applications working on and with the appropriately represented and delivered background knowledge. Each of these pillars will yield innovative methods and tools during the project runtime until 2013. We propose a concept draft and a working plan covering the next twelve months for an integrative architecture of a Corporate Semantic Web provided by these three core pillars.

Swarm Approaches for Semantic Triple Clustering and Retrieval in Distributed RDF Spaces

Sebastian Koske

Institut für Informatik | 2009-02

PDF 3 MB, acceptable qualityPDF 25 MB, high quality

This thesis implements and evaluates swarm-based approaches for semantic Tuple Spaces, based on the previous work of Daniel Graff, who implemented a LINDA Tuple Space system called SwarmLinda. It extends this space with semantic triple clustering and retrieval by dapting common similarity measures for a distributed swarm-based architecture and by developing research strategies inspired by ant routing algorithms.

Gray Code Compression

Darko Dimitrov, Tomáš Dvořák, Petr Gregor, and Riste Škrekovski

Takustraße 9, 14195 Berlin: Fachbereich Mathematik und Informatik, Institut für Informatik, Freie Universität Berlin | 2009-03

Gray Code Compression

An n-bit (cyclic) Gray code is a (cyclic) sequence of all n-bit strings such that consecutive strings differ in a single bit. We describe an algorithm which for every positive integer n constructs an n-bit cyclic Gray code whose graph of transitions is the d-dimensional hypercube Qd if n = 2^d, or a subgraph of Qd if 2^d−1 < n < 2^d. This allows to compress sequences that follow this code so that only Theta (log log n) bits per n-bit string are needed.

Construction Sequences and Certifying 3-Connectedness

Jens M. Schmidt

Takustraße 9, 14195 Berlin: Freie Universität Berlin, Institut für Informatik | 2009-01

Construction Sequences and Certifying ...

Given two 3-connected graphs G and H, a construction sequence constructs G from H (e. g. from the K4) with three basic operations, called the Barnette-Grünbaum operations. These operations are known to be able to construct all 3-connected graphs. We extend this result by identifying every intermediate graph in the construction sequence with a subdivision in G and showing under some minor assumptions that there is still a construction sequence to G when we start from an arbitrary prescribed H-subdivision. This leads to the first algorithm that computes a construction sequence in time O(|V (G)|2). As an application, we develop a certificate for the 3-connectedness of graphs that can be easily computed and verified. Based on this, a certifying test on 3-connectedness is designed.

Thema: construction sequence, 3-connected graph, nested subdivisions, inductive characterization, 3-connectedness, certifying algorithm


Please note:

The official publishing point of Freie Universität Berlin, and thus also for our Technical Reports, is the Edocs-Server, Technical Reports, series B.

This site here is maintained for historic purposes, but will not completely cover publications from 2009 onwards.

Intern: Hinweise zum Einreichen neuer Technical Reports