On Alternating Non-Context-Free Grammars

We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.

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.

Angepasste Kommunikationssysteme für den effizienten Einsatz in dezentralen elektrischen Versorgungsstrukturen

Angepasste Kommunikationssysteme für den effizienten Einsatz in dezentralen elektrischen Versorgungsstrukturen - In öffentlichen Elektrizitätsnetzen wird der Informationsaustausch seit längerem durch historisch gewachsene und angepasste Systeme erfolgreich bewerkstelligt. Basierend auf einem weiten Erfahrungsspektrum und einer gut ausgebauten Kommunikationsinfrastruktur stellt die informationstechnische Anbindung eines Teilnehmers im öffentlichen Versorgungsnetz primär kein Hemmnis dar. Anders gestaltet sich dagegen die Situation in dezentralen Versorgungsstrukturen. Da die Elektrifizierung von dezentralen Versorgungsgebieten, mittels der Vernetzung vieler verteilter Erzeugungsanlagen und des Aufbaus von nicht an das öffentliche Elektrizitätsnetz angeschlossenen Verteilnetzen (Minigrids), erst in den letzten Jahren an Popularität gewonnen hat, sind nur wenige Projekte bis dato abgeschlossen. Für die informationstechnische Anbindung von Teilnehmern in diesen Strukturen bedeutet dies, dass nur in einem sehr begrenzten Umfang auf Erfahrungswerte bei der Systemauswahl zurückgegriffen werden kann. Im Rahmen der Dissertation ist deshalb ein Entscheidungsfindungsprozess (Leitfaden für die Systemauswahl) entwickelt worden, der neben einem direkten Vergleich von Kommunikationssystemen basierend auf abgeleiteten Bewertungskriterien und Typen, der Reduktion des Vergleichs auf zwei Systemwerte (relativer Erwartungsnutzenzuwachs und Gesamtkostenzuwachs), die Wahl eines geeigneten Kommunikationssystems für die Applikation in dezentralen elektrischen Versorgungsstrukturen ermöglicht. In Anlehnung an die klassische Entscheidungstheorie werden mit der Berechnung eines Erwartungsnutzens je Kommunikationssystems, aus der Gesamtsumme der Einzelprodukte der Nutzwerte und der Gewichtungsfaktor je System, sowohl die technischen Parameter und applikationsspezifischen Aspekte, als auch die subjektiven Bewertungen zu einem Wert vereint. Mit der Ermittlung der jährlich erforderlichen Gesamtaufwendungen für ein Kommunikationssystem bzw. für die anvisierten Kommunikationsaufgaben, in Abhängigkeit der Applikation wird neben dem ermittelten Erwartungsnutzen des Systems, ein weiterer Entscheidungsparameter für die Systemauswahl bereitgestellt. Die anschließende Wahl geeigneter Bezugsgrößen erlaubt die Entscheidungsfindung bzgl. der zur Auswahl stehenden Systeme auf einen Vergleich mit einem Bezugssystem zurückzuführen. Hierbei sind nicht die absoluten Differenzen des Erwartungsnutzen bzw. des jährlichen Gesamtaufwandes von Interesse, sondern vielmehr wie sich das entsprechende System gegenüber dem Normal (Bezugssystem) darstellt. Das heißt, der relative Zuwachs des Erwartungsnutzen bzw. der Gesamtkosten eines jeden Systems ist die entscheidende Kenngröße für die Systemauswahl. Mit dem Eintrag der berechneten relativen Erwartungsnutzen- und Gesamtkostenzuwächse in eine neu entwickelte 4-Quadranten-Matrix kann unter Berücksichtigung der Lage der korrespondierenden Wertepaare eine einfache (grafische) Entscheidung bzgl. der Wahl des für die Applikation optimalsten Kommunikationssystems erfolgen. Eine exemplarisch durchgeführte Systemauswahl, basierend auf den Analyseergebnissen von Kommunikationssystemen für den Einsatz in dezentralen elektrischen Versorgungsstrukturen, veranschaulicht und verifiziert die Handhabung des entwickelten Konzeptes. Die abschließende Realisierung, Modifikation und Test des zuvor ausgewählten Distribution Line Carrier Systems unterstreicht des Weiteren die Effizienz des entwickelten Entscheidungsfindungsprozesses. Dem Entscheidungsträger für die Systemauswahl wird insgesamt ein Werkzeug zur Verfügung gestellt, das eine einfache und praktikable Entscheidungsfindung erlaubt. Mit dem entwickelten Konzept ist erstmals eine ganzheitliche Betrachtung unter Berücksichtigung sowohl der technischen und applikationsspezifischen, als auch der ökonomischen Aspekte und Randbedingungen möglich, wobei das Entscheidungsfindungskonzept nicht nur auf die Systemfindung für dezentrale elektrische Energieversorgungsstrukturen begrenzt ist, sondern auch bei entsprechender Modifikation der Anforderungen, Systemkenngrößen etc. auf andere Applikationsanwendungen übertragen werden.

Design, implementation and application of a generic framework for integrated regional land-use modeling

Land use is a crucial link between human activities and the natural environment and one of the main driving forces of global environmental change. Large parts of the terrestrial land surface are used for agriculture, forestry, settlements and infrastructure. Given the importance of land use, it is essential to understand the multitude of influential factors and resulting land use patterns. An essential methodology to study and quantify such interactions is provided by the adoption of land-use models. By the application of land-use models, it is possible to analyze the complex structure of linkages and feedbacks and to also determine the relevance of driving forces. Modeling land use and land use changes has a long-term tradition. In particular on the regional scale, a variety of models for different regions and research questions has been created. Modeling capabilities grow with steady advances in computer technology, which on the one hand are driven by increasing computing power on the other hand by new methods in software development, e.g. object- and component-oriented architectures. In this thesis, SITE (Simulation of Terrestrial Environments), a novel framework for integrated regional sland-use modeling, will be introduced and discussed. Particular features of SITE are the notably extended capability to integrate models and the strict separation of application and implementation. These features enable efficient development, test and usage of integrated land-use models. On its system side, SITE provides generic data structures (grid, grid cells, attributes etc.) and takes over the responsibility for their administration. By means of a scripting language (Python) that has been extended by language features specific for land-use modeling, these data structures can be utilized and manipulated by modeling applications. The scripting language interpreter is embedded in SITE. The integration of sub models can be achieved via the scripting language or by usage of a generic interface provided by SITE. Furthermore, functionalities important for land-use modeling like model calibration, model tests and analysis support of simulation results have been integrated into the generic framework. During the implementation of SITE, specific emphasis was laid on expandability, maintainability and usability. Along with the modeling framework a land use model for the analysis of the stability of tropical rainforest margins was developed in the context of the collaborative research project STORMA (SFB 552). In a research area in Central Sulawesi, Indonesia, socio-environmental impacts of land-use changes were examined. SITE was used to simulate land-use dynamics in the historical period of 1981 to 2002. Analogous to that, a scenario that did not consider migration in the population dynamics, was analyzed. For the calculation of crop yields and trace gas emissions, the DAYCENT agro-ecosystem model was integrated. In this case study, it could be shown that land-use changes in the Indonesian research area could mainly be characterized by the expansion of agricultural areas at the expense of natural forest. For this reason, the situation had to be interpreted as unsustainable even though increased agricultural use implied economic improvements and higher farmers' incomes. Due to the importance of model calibration, it was explicitly addressed in the SITE architecture through the introduction of a specific component. The calibration functionality can be used by all SITE applications and enables largely automated model calibration. Calibration in SITE is understood as a process that finds an optimal or at least adequate solution for a set of arbitrarily selectable model parameters with respect to an objective function. In SITE, an objective function typically is a map comparison algorithm capable of comparing a simulation result to a reference map. Several map optimization and map comparison methodologies are available and can be combined. The STORMA land-use model was calibrated using a genetic algorithm for optimization and the figure of merit map comparison measure as objective function. The time period for the calibration ranged from 1981 to 2002. For this period, respective reference land-use maps were compiled. It could be shown, that an efficient automated model calibration with SITE is possible. Nevertheless, the selection of the calibration parameters required detailed knowledge about the underlying land-use model and cannot be automated. In another case study decreases in crop yields and resulting losses in income from coffee cultivation were analyzed and quantified under the assumption of four different deforestation scenarios. For this task, an empirical model, describing the dependence of bee pollination and resulting coffee fruit set from the distance to the closest natural forest, was integrated. Land-use simulations showed, that depending on the magnitude and location of ongoing forest conversion, pollination services are expected to decline continuously. This results in a reduction of coffee yields of up to 18% and a loss of net revenues per hectare of up to 14%. However, the study also showed that ecological and economic values can be preserved if patches of natural vegetation are conservated in the agricultural landscape. -----------------------------------------------------------------------

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.

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.

Eine SPARQL-Schnittstelle für OData-Services

Enterprise-Resource-Planning-Systeme (ERP-Systeme) bilden für die meisten mittleren und großen Unternehmen einen essentiellen Bestandteil ihrer IT-Landschaft zur Verwaltung von Geschäftsdaten und Geschäftsprozessen. Geschäftsdaten werden in ERP-Systemen in Form von Geschäftsobjekten abgebildet. Ein Geschäftsobjekt kann mehrere Attribute enthalten und über Assoziationen zu anderen Geschäftsobjekten einen Geschäftsobjektgraphen aufspannen. Existierende Schnittstellen ermöglichen die Abfrage von Geschäftsobjekten, insbesondere mit Hinblick auf deren Attribute. Die Abfrage mit Bezug auf ihre Position innerhalb des Geschäftsobjektgraphen ist jedoch über diese Schnittstellen häufig nur sehr schwierig zu realisieren. Zur Vereinfachung solcher Anfragen können semantische Technologien, wie RDF und die graphbasierte Abfragesprache SPARQL, verwendet werden. SPARQL ermöglicht eine wesentlich kompaktere und intuitivere Formulierung von Anfragen gegen Geschäftsobjektgraphen, als es mittels der existierenden Schnittstellen möglich ist. Die Motivation für diese Arbeit ist die Vereinfachung bestimmter Anfragen gegen das im Rahmen dieser Arbeit betrachtete SAP ERP-System unter Verwendung von SPARQL. Zur Speicherung von Geschäftsobjekten kommen in ERP-Systemen typischerweise relationale Datenbanken zum Einsatz. Die Bereitstellung von SPARQL-Endpunkten auf Basis von relationalen Datenbanken ist ein seit längerem untersuchtes Gebiet. Es existieren verschiedene Ansätze und Tools, welche die Anfrage mittels SPARQL erlauben. Aufgrund der Komplexität, der Größe und der Änderungshäufigkeit des ERP-Datenbankschemas können solche Ansätze, die direkt auf dem Datenbankschema aufsetzen, nicht verwendet werden. Ein praktikablerer Ansatz besteht darin, den SPARQL-Endpunkt auf Basis existierender Schnittstellen zu realisieren. Diese sind weniger komplex als das Datenbankschema, da sie die direkte Abfrage von Geschäftsobjekten ermöglichen. Dadurch wird die Definition des Mappings erheblich vereinfacht. Das ERP-System bietet mehrere Schnittstellen an, die sich hinsichtlich des Aufbaus, der Zielsetzung und der verwendeten Technologie unterscheiden. Unter anderem wird eine auf OData basierende Schnittstelle zur Verfügung gestellt. OData ist ein REST-basiertes Protokoll zur Abfrage und Manipulation von Daten. Von den bereitgestellten Schnittstellen weist das OData-Interface gegenüber den anderen Schnittstellen verschiedene Vorteile bei Realisierung eines SPARQL-Endpunktes auf. Es definiert eine Abfragesprache und einen Link-Adressierungsmechanismus, mit dem die zur Beantwortung einer Anfrage benötigten Service-Aufrufe und die zu übertragende Datenmenge erheblich reduziert werden können. Das Ziel dieser Arbeit besteht in der Entwicklung eines Verfahrens zur Realisierung eines SPARQL-Endpunktes auf Basis von OData-Services. Dazu wird zunächst eine Architektur vorgestellt, die als Grundlage für die Implementierung eines entsprechenden Systems dienen kann. Ausgehend von dieser Architektur, werden die durch den aktuellen Forschungsstand noch nicht abgedeckten Bereiche ermittelt. Nach bestem Wissen ist diese Arbeit die erste, welche die Abfrage von OData-Schnittstellen mittels SPARQL untersucht. Dabei wird als Teil dieser Arbeit ein neuartiges Konzept zur semantischen Beschreibung von OData-Services vorgestellt. Dieses ermöglicht die Definition von Abbildungen der von den Services bereitgestellten Daten auf RDF-Graphen. Aufbauend auf den Konzepten zur semantischen Beschreibung wird eine Evaluierungssemantik erarbeitet, welche die Auflösung von Ausdrücken der SPARQL-Algebra gegen semantisch annotierte OData-Services definiert. Dabei werden die Daten aller OData-Services ermittelt, die zur vollständigen Abarbeitung einer Anfrage benötigt werden. Zur Abfrage der relevanten Daten wurden Konzepte zur Erzeugung der entsprechenden OData-URIs entwickelt. Das vorgestellte Verfahren wurde prototypisch implementiert und anhand zweier Anwendungsfälle für die im betrachteten Szenario maßgeblichen Servicemengen evaluiert. Mit den vorgestellten Konzepten besteht nicht nur die Möglichkeit, einen SPARQL-Endpunkt für ein ERP-System zu realisieren, vielmehr kann jede Datenquelle, die eine OData-Schnittstelle anbietet, mittels SPARQL angefragt werden. Dadurch werden große Datenmengen, die bisher für die Verarbeitung mittels semantischer Technologien nicht zugänglich waren, für die Integration mit dem Semantic Web verfügbar gemacht. Insbesondere können auch Datenquellen, deren Integration miteinander bisher nicht oder nur schwierig möglich war, über Systeme zur föderierten Abfrage miteinander integriert werden.