The Golog action programming language is a powerful means to express high-level behaviours in terms of programs over actions defined in a Situation Calculus theory. In particular for physical systems, verifying that the program satisfies certain desired temporal properties is often crucial, but undecidable in general, the latter being due to the language’s high expressiveness in terms of first-order quantification and program constructs. So far, approaches to achieve decidability involved restrictions where action effects either had to be contextfree (i.e. not depend on the current state), local (i.e. only affect objects mentioned in the action’s parameters), or at least bounded (i.e. only affect a finite number of objects). In this paper, we present a new, more general class of action theories (called acyclic) that allows for context-sensitive, non-local, unbounded effects, i.e. actions that may affect an unbounded number of possibly unnamed objects in a state-dependent fashion. We contribute to the further exploration of the boundary between decidability and undecidability for Golog, showing that for acyclic theories in the two-variable fragment of first-order logic, verification of CTL properties of programs over ground actions is decidable.

In der Bioinformatik und der Next-Generation Sequenzierung benötigen wir oft große und komplexe Verarbeitungsabläufe um Daten zu analysieren. Die Werkzeuge und Bibliotheken, die hierin die Verarbeitungsschritte bilden, stammen aus unterschiedlichen Quellen und exponieren unterschiedliche Schnittstellen, was ihre Integration in Datenanalyseplattformen erschwert. Hinzu kommt, dass diese Verarbeitungsabläufe meist große Datenmengen prozessieren weshalb Forscher erwarten, dass unabhängige Verarbeitungsschritte parallel laufen. Der Stand der Technik im Feld der wissenschaftlichen Datenverarbeitung für Bioinformatik und Next-Generation Sequenzierung sind wissenschaftliche Workflowsysteme. Ein wissenschaftliches Workflowsystem erlaubt es Forschern Verarbeitungsabläufe als Workflow auszudrücken. Solch ein Workflow erfasst die Datenabhängigkeiten in einem Verarbeitungsablauf, integriert externe Software und erlaubt es unabhängige Verarbeitungsschritte zu erkennen, um sie parallel auszuführen. In dieser Arbeit präsentieren wir Cuneiform, eine Workflowsprache, und ihre verteilte Ausführungsumgebung. Für Cuneiform's Design nehmen wir die Perspektive der Programmiersprachentheorie ein. Wir lassen Methoden der funktionalen Programmierung einfließen um Komposition und Datenabhängigkeiten auszudrücken. Wir nutzen operationelle Semantiken um zu definieren, wann ein Workflow wohlgeformt und konsistent ist und um Reduktion zu erklären. Für das Design der verteilten Ausführungsumgebung nehmen wir die Perspektive der verteilten Systeme ein. Wir nutzen Petri Netze um die Kommunikationsstruktur der im System beteiligten Agenten zu erklären. / Bioinformatics and next-generation sequencing data analyses often form large and complex pipelines. The tools and libraries making up the processing steps in these pipelines come from different sources and have different interfaces which hampers integrating them into data analysis frameworks. Also, these pipelines process large data sets. Thus, users need to parallelize independent processing steps. The state of the art in large-scale scientific data analysis for bioinformatics and next-generation sequencing are scientific workflow systems. A scientific workflow system allows researchers to describe a data analysis pipeline as a scientific workflow which integrates external software, defines the data dependencies forming a data analysis pipeline, and parallelizes independent processing steps. Scientific workflow systems consist of a workflow language providing a user interface, and an execution environment. The workflow language determines how users express workflows, reuse and compose workflow fragments, integrate external software, how the scientific workflow system identifies independent processing steps, and how we derive optimizations from a workflow's structure. The execution environment schedules and runs data processing operations. In this thesis we present Cuneiform, a workflow language, and its distributed execution environment. For Cuneiform's design we take the perspective of programming languages. We adopt methods from functional programming towards composition and expressing data dependencies. We apply operational semantics and type systems to define well-formedness, consistency, and reduction of Cuneiform workflows. For the design of the distributed execution environment we take the perspective of distributed systems. We apply Petri nets to define the communication patterns among the distributed execution environment's agents.

Simulationssprachen sind in Bezug auf die Unterstützung neuer domänenspezifischer Konzepte mit einer dem Problem entsprechenden prägnanten Darstellung nicht flexibel erweiterbar. Dies betrifft sowohl die Sprache in ihren Konzepten als auch die Unterstützung der Sprache durch Sprachwerkzeuge. In dieser Arbeit entsteht der neue Sprachentwicklungsansatz Discrete-Event Modelling with Extensibility (DMX) für die Entwicklung flexibel erweiterbarer Simulationssprachen für domänenspezifische Anwendungsfelder, der eine effiziente Entwicklung der Sprache und eine effiziente Ausführung von Modellen erlaubt. Der Fokus der Arbeit liegt auf der zeitdiskreten ereignisbasierten Simulation und einer prozessorientierten Beschreibung von Simulationsmodellen. Der Ansatz unterscheidet Basiskonzepte, die zur Basissprache gehören, und Erweiterungskonzepte, die Teil von Erweiterungsdefinitionen sind. Es wird untersucht, welche Basiskonzepte eine Simulationssprache bereitstellen muss, so dass eine laufzeiteffiziente Ausführung von prozessorientierten Modellen möglich ist. Die hohe Laufzeiteffizienz der Ausführung wird durch die Konzeption einer neuartigen Methode zur Abbildung von Prozesskontextwechseln auf ein C++-Programm gezeigt. Der Spracherweiterungsansatz ist nicht auf Simulationssprachen als Basissprachen beschränkt und wird daher allgemein beschrieben. Der Ansatz basiert auf einer Syntaxerweiterung einer Basissprache, die mit einem Metamodell und einer kontextfreien Grammatik definiert ist. Die Ausführung von Erweiterungskonzepten wird durch eine Konzeptreduktion auf Basiskonzepte erreicht. Der Ansatz stellt bestimmte Voraussetzungen an eine Basissprache und erlaubt bestimmte Arten von Erweiterungen, die in der Arbeit untersucht werden. Die Eignung des Anstatzes zur Entwicklung einer komplexen domänenspezifischen Simulationssprache wird an einer Sprache für Zustandsautomaten gezeigt. / Simulation languages are not extensible regarding the support of new domain-specific concepts with a concise representation. This includes the concepts of a language as well as the language tools. In this dissertation, the new approach Discrete-Event Modelling with Extensibility (DMX) is developed. DMX allows to create flexible domain-specific simulation languages by defining extensions to a base language. The approach allows to develop these languages efficiently and also to execute simulation models in a runtime efficient way. The focus of this dissertation is on process-oriented descriptions of discrete-event simulation models. The approach distinguishes base concepts which are part of the base language and extension concepts which are part of extension definitions. The dissertation investigates the necessary base concepts which should be included in a base simulation language in order to execute process-oriented models efficiently. The high runtime efficiency of executions is achieved by creating a new method for mapping process context switches to a program in C++. The runtime efficiency can be transferred to extension concepts as well. The extension approach is described in a general way because it is not limited to a simulation language as a base language. The approach is based on the syntax extension of a base language, which is defined by a metamodel and a context-free grammar. The execution of extension concepts is achieved by concept reduction to base concepts. The approach has a number of requirements to the base language and allows certain kinds of extensions, which are desribed in the dissertation. The possibility to define a complex domain-specific simulation language is shown by applying the approach to the development of a state machine language.

Mit mehr als 120 Millionen registrierten Internetadressen (Stand: März 2007) symbolisiert das Internet heutzutage das größte Informationsmedium unserer Zeit. Täglich wächst das Internet um eine unüberschaubare Menge an Informationen. Diese Informationen sind häufig in Dokumenten hinterlegt, welche zur Auszeichnung die Hypertext Markup Language verwenden. Seit Beginn der Neunziger Jahre hat sich dieses System bewährt, da dadurch der einzelne Nutzer in die Lage versetzt wird, auf einfache und effiziente Weise Dokumentinhalte mit Darstellungsanweisungen zu versehen und diese eigenständig im Internet zu veröffentlichen. Diese Layoutinformationen können bei Abruf der entsprechenden Ressource durch ein Computerprogramm leicht ausgewertet und zur Darstellung der Inhalte genutzt werden. Obwohl sowohl die Layoutinformationen als auch die eigentlichen Dokumentinhalte in einem textuellen Format vorliegen, konnten die Nutzertextinhalte durch eine Maschine bisher nur sehr eingeschränkt verarbeitet werden. Während es menschlichen Nutzern keinerlei Probleme bereitet, die Bedeutung einzelner Texte auf einer Webseite zu identifizieren, stellen diese für einen Rechner prinzipiell nur eine Aneinanderreihung von ASCII-Zeichen dar. Sobald es möglich werden würde, die Bedeutung von Informationen durch ein Computerprogramm effizient zu erfassen und weiterzuverarbeiten, wären völlig neue Anwendungen mit qualitativ hochwertigeren Ergebnissen im weltweiten Datennetz möglich. Nutzer könnten Anfragen an spezielle Agenten stellen, welche sich selbstständig auf die Suche nach passenden Resultaten begeben; Informationen verschiedener Informationsquellen könnten nicht nur auf semantischer Ebene verknüpft, sondern daraus sogar neue, nicht explizit enthaltene Informationen abgeleitet werden. Ansätze dazu, wie Dokumente mit semantischen Metadaten versehen werden können, gibt es bereits seit einiger Zeit. Lange umfasste dies jedoch die redundante Bereitstellung der Informationen in einem eigenen Dokumentenformat, weswegen sich keines der Konzepte bis in den Privatbereich durchsetzen konnte und als Endkonsequenz in den vergangenen Monaten besonderes Forschungsinteresse darin aufkam, Möglichkeiten zu finden, wie semantische Informationen ohne großen Zusatzaufwand direkt in bestehende HTML-Dokumente eingebettet werden können. Die vorliegende Diplomarbeit möchte diese neuen Möglichkeiten im Bereich des kollaborativen Arbeitens näher untersuchen. Ziel ist es dazu, eine Webapplikation zur Abwicklung typischer Projektmanagement-Aufgaben zu entwickeln, welche jegliche Informationen unter einem semantischen Gesichtspunkt analysieren, aufbereiten und weiterverarbeiten kann und unabhängig von der konkreten Anwendungsdomain und Plattform systemübergreifend eingesetzt werden kann. Die Konzepte Microformats und RDFa werden dabei besonders herausgestellt und nach Schwächen und zukünftigen Potentialen hin untersucht. / The World Wide Web supposably symbolizes with currently more than 120 million registered internet domains (March 2007) the most comprehensive information reference of all times. The amount of information available increases by a storming bulk of data ever day. Those information is often embedded in documents which utilize the Hypertext Markup Language. This enables the user to mark out certain layout properties of a text in an easy and efficient fashion and to publish the final document containing both layout and data information. A computer application is then able to extract style information from the document resource and to use it in order to render the resulting website. Although layout information and data are both equally represented in a textual manner, a machine was hardly capable of processing user content so far. Whereas human consumers have no problem to identify and understand the sense of several paragraphs on a website, they basically represent only a concatenation of ASCII characters for a machine. If it were possible to efficiently disclose the sense of a word or phrase to a computer program in order to process it, new astounding applications with output results of high quality would be possible. Users could create queries for specialized agents which autonomously start to search the web for adequate result matches. Moreover, the data of multiple information sources could be linked and processed together on a semantic level so that above all new, not explicitly stated information could be inferred. Approaches already exist, how documents could be enhanced with semantic metadata, however, many of these involve the redundant provision of those information in a specialized document format. As a consequence none of these concepts succeeded in becoming a widely used method and research started again to find possibilities how to embed semantic annotations without huge additional efforts in an ordinary HTML document. The present thesis focuses on an analysis of these new concepts and possibilities in the area of collaborative work. The objective is to develop the prototype of a web application with which it is possible to manage typical challenges in the realm of project and workflow management. Any information available should be processable under a semantic viewpoint which includes analysis, conditioning and reuse independently from a specific application domain and a certain system platform. Microformats and RDFa are two of those relatively new concepts which enable an application to extract semantic information from a document resource and are therefore particularly exposed and compared with respect to advantages and disadvantages in the context of a “Semantic Web”.

Präsenzbewertung im Kommunikationsraum der Telefonie ist ein zunehmend wichtiges Gebiet der Forschung. Ziel der Dissertation ist es, sich dem natürlichen Kommunikationsraum der verbalen und nonverbalen Kommunikation anzunähern. Im Kommunikationsraum Telefonie existieren noch keine Verfahren, die unterschiedliche Dringlichkeiten von Anrufen wiedergeben. Momentan ist die Signalart ausschließlich davon abhängig, wie der Angerufene sein Mobiltelefon eingestellt hat. In der Arbeit wurde ein Verfahren entwickelt, das unmittelbar vor der Signalisierung eines Anrufes die Signalart abhängig vom Kontext des Angerufenen individuell ermittelt und automatisch einstellt. Dabei werden Algorithmen aus dem Bereich der KI verwendet. Mit Hilfe von Lernalgorithmen werden die Ergebnisse der Präsenzbewertung kontinuierlich verbessert. Im Rahmen eines Experimentes konnten Präzisionen bei sechs verschiedenen Signalarten von bis zu 73 % erreicht werden. Dieses Verfahren ermöglicht eine deutliche Annäherung an den natürlichen Kommunikationsraum.

Terrain surfaces conserve human activities in terms of textures and structures. With reference to archaeological questions, the geological archive is investigated by means of models regarding anthropogenic traces. In doing so, the high-resolution digital terrain model is of inestimable value for the decoding of the archive. The evaluation of these terrain models and the reconstruction of historical surfaces is still a challenging issue. Due to the data collection by means of LiDAR systems (light detection and ranging) and despite their subsequent pre-processing and filtering, recently anthropogenic artefacts are still present in the digital terrain model. Analysis have shown that elements, such as contour lines and channels, can well be extracted from a highresolution digital terrain model. This way, channels in settlement areas show a clear anthropogenic character. This fact can also be observed for contour lines. Some contour lines representing a possibly natural ground surface and avoid anthropogenic artefacts. Comparable to channels, noticeable patterns of contour lines become visible in areas with anthropogenic artefacts. The presented work ow uses functionalities of ArcGIS and the programming language R.¹ The method starts with the extraction of contour lines from the digital terrain model. Through macroscopic analyses based on geomorphological expert knowledge, contour lines are selected representing the natural geomorphological character of the surface. In a first step, points are determined along each contour line in regular intervals. This points and the corresponding height information which is taken from an original digital terrain model is saved as a point cloud. Using the programme library gstat, a variographic analysis and the use of a Kriging-procedure based on this follow. The result is a digital terrain model filtered considering geomorphological expert knowledge showing no human degradation in terms of artefacts, preserving the landscape-genetic character and can be called a prehistoric terrain model.

Currently in archaeological studies digital elevation models are mainly used especially in terms of shaded reliefs for the prospection of archaeological sites. Hesse (2010) provides a supporting software tool for the determination of local relief models during the prospection using LiDAR scans. Furthermore the search for relicts from WW2 is also in the focus of his research.¹ In James et al. (2006) the determined contour lines were used to reconstruct locations of archaeological artefacts such as buildings.² This study is much more and presents an innovative workflow of determining historical high resolution terrain surfaces using recent high resolution terrain models and sedimentological expert knowledge. Based on archaeological field studies (Franconian Saale near Bad Neustadt in Germany) the sedimentological analyses shows that archaeological interesting horizon and geomorphological expert knowledge in combination with particle size analyses (Köhn, DIN ISO 11277) are useful components for reconstructing surfaces of the early Middle Ages.³ Furthermore the paper traces how it is possible to use additional information (extracted from a recent digital terrain model) to support the process of determination historical surfaces. Conceptual this research is based on methodology of geomorphometry and geo-statistics. The basic idea is that the working procedure is based on the different input data. One aims at tracking the quantitative data and the other aims at processing the qualitative data. Thus, the first quantitative data were available for further processing, which were later processed with the qualitative data to convert them to historical heights. In the final stage of the work ow all gathered information are stored in a large data matrix for spatial interpolation using the geostatistical method of Kriging. Besides the historical surface, the algorithm also provides a first estimation of accuracy of the modelling. The presented workflow is characterized by a high exibility and the opportunity to include new available data in the process at any time.

Die vorliegende Arbeit analysiert die Phänologie photosynthetisch aktiver Vegetation mit Hilfe von NDVI Zeitreihen für einen Zeitraum von 24 Jahren (AVHRR‑GIMMS Daten). Neben einer Datierung des jahreszeitlichen Wechsels zwischen Wachstums-, Reife- und Seneszenzphase wird das Ziel verfolgt, Trends sowohl in phänologischen Ereignissen (Start-of-Season) als auch im NDVI zu identifizieren. Das, in der semi-ariden Sahelregion gelegene, Untersuchungsgebiet weist mit zwei sich teilweise überlagernden Vegetationsperioden eine komplexe Phänologie auf, deren Modellierung durch die sowohl in ihren Zeitpunkten als auch in ihren Ausprägungen hoch variablen Vegetationsabläufe erschwert wird. Vor diesem Hintergrund ist zunächst ein, auf der Fourieranalyse basierender, Ansatz zur flexiblen Glättung der NDVI Zeitreihen entwickelt worden. Um für die Trendanalyse lineare Regressionsverfahren einsetzen zu können, sind die Zeitreihen nach dem Komponentenmodell untergliedert worden (Subtraktion der Saisonfigur). Alternativ kam der saisonale MANN-KENDALL Trendtest zur Anwendung. Die NDVI Zeitreihen wurden ebenfalls auf Änderungen im mehrjährigen Mittelwert (Bruchpunkte) untersucht. Alle Auswertungen sind in einer eigenen Applikation umgesetzt worden. Es konnte gezeigt werden, daß Änderungen im NDVI Niveau eher abrupt als graduell verlaufen. Langfristige Trends weisen nur geringe Anstiege auf. Die Vegetation erholte sich von der Dürre 1984/85 nur im südlichen Teil des Untersuchungsgebietes, im Norden dominieren langfristig negative Trends. Brüche im mean der NDVI Zeitreihen korrelieren mit Brüchen im Abflußverhalten des Niger.

In this thesis we see two new approaches to compose tree transducers and more general to fuse functional programs. The first abroach is based on initial algebras. We prove a new variant of the acid rain theorem for mutually recursive functions where the build function is substituted by a concrete functor. Moreover, we give a symmetric form (i.e. consumer and producer have the same syntactic form) of our new acid rain theorem where fusion is composition in a category and thus in particular associative. Applying this to compose top-down tree transducers yields the same result (on a syntactic level) as the classical top-down tree transducer composition. The second approach is based on free monads and monad transformers. In the same way as monoids are used in the theory of character string automata, we use monads in the theory of tree transducers. We generalize the notion of a tree transducer defining the monadic transducer, and we prove an according fusion theorem. Moreover, we prove that homomorphic monadic transducers are semantically equivalent. The latter makes it possible to compose syntactic classes of tree transducers (or particular functional programs) by simply composing endofunctors.

„Remote Scripting“-Anwendungen erleben seit einigen Jahren einen regelrechten Anfrageboom. Während aus usability-Sicht bisher eine strikte Unterscheidung zwischen Desktop-Anwendungen und Webapplikationen herrschte, finden sich seit einiger Zeit zunehmend Angebote im World Wide Web, die diese strikte Trennung verwischen lassen. Interaktive Nutzerdialoge, nebenläufige Prozessabarbeitung und visuelle Unterstützungsmittel wie Drag & Drop- Effekte halten auf Webseiten Einzug, die dem Nutzer bisher nur aus eigenständigen Softwareprodukten in einer spezifischen Betriebssystemumgebung bekannt waren. Viele dieser neuen Anwendungs- und Interaktionsmöglichkeiten im weltweiten Datennetz werden inzwischen unter dem Oberbegriff Web 2.0 zusammengefasst. Für den Nutzer bringt dieser neue Entwicklungstrend viele Vorteile: Ansprechende, intuitive Nutzerführungen ohne die Notwendigkeit, eine ganze Internetseite bei jedem Interaktionsschritt neu zu laden und ohne bemerkbaren zeitlichen Overhead. Was für den Nutzer Erleichterung bringen soll, bedeutet häufig für einen Programmierer zunächst Mehraufwand. Eine Technik zur Realisierung solcher so genannten Rich Internet Applications, die sich in den letzten beiden Jahren immer mehr in den Vordergrund gedrängt hat, wird unter der Bezeichnung AJAX zusammengefasst. Einen einheitlichen Standard gibt es dabei nicht, sodass fast täglich neue AJAX-basierte frameworks veröffentlicht werden, die dem Programmierer (wenigstens einen Teil der) Komplexität der Programmflusssteuerung abnehmen sollen. Aufgabe der Studienarbeit soll es daher sein, das inzwischen unüberschaubar gewordene Angebot an AJAX frameworks zu systematisieren und einen Überblick über Vor- und Nachteile ausgewählter Programmbibliotheken zu geben. Dafür ist ein Kriterienkatalog zu erarbeiten, der eine Bewertung der verschiedenen frameworks nach unterschiedlichen Gesichtspunkten ermöglicht. Besonderer Schwerpunkt ist dabei auf Kriterien aus Programmierersicht (Sprachunabhängigkeit, Overhead, Implementierungsmöglichkeiten,…) und Anwendersicht (Plattformanforderungen, Einarbeitungszeit, Ergebnisqualität, …) zu legen. Auf den Kriterienkatalog ist anschließend eine Auswahl an bereits existierenden, frei verfügbaren AJAX frameworks anzuwenden, die als zukünftig relevant eingeschätzt werden. Die Ergebnisse sind abschließend in einer Gesamtübersicht zu präsentieren, die eine objektive Empfehlung für Nutzer darstellen soll, die vor der Wahl stehen, welche AJAX Programmbibliothek sie zukünftig einsetzen sollten.