Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

Vorausschau und Planung neuer Technologiepfade in Unternehmen

Unternehmen konkurrieren in einem globalen Wettbewerb um den Transfer neuer Technologien in erfolgreiche Geschäftsmodelle. Aus diesem Grund stehen sie zunehmend der Herausforderung gegenüber, technologische Potenziale frühzeitig zu identifizieren, zu bewerten und Strategien für das Erschließen dieser Potenziale zu entwickeln. Dies ist zentraler Gegenstand der Vorausschau und Planung neuer Technologiepfade. In der vorliegenden Arbeit wird gemeinsam mit vier Unternehmen ein Leitfaden für die Strategiefindung, Entwicklung und Kommerzialisierung neu aufkommender Technologien entwickelt und angewendet. Den Ausgangspunkt der Arbeit bildet eine systematische Aufarbeitung des Forschungsstandes der Vorausschau und Planung neuer Technologien. Anschließend wird ein Beschreibungsmodell der Entstehung neuer Technologiepfade in technologiebasierten Innovationssystemen entwickelt. Auf Basis dieses Modells werden unterschiedliche Kategorien von Einflussfaktoren definiert, die als Analyserahmen für die neu entstehende Technologie dienen. Auf Basis der in der Literatur dokumentierten Abläufe, Teamstrukturen und Methoden (z.B. Roadmaps, Szenarien, Datenbankanalysen) wird ein sechsstufiger Ansatz für die Durchführung der Vorausschau und Planung neuer Technologiepfade konzipiert. Dieser Ansatz wird in vier Firmen für die Vorausschau und Planung neuer Technologien angewendet. Die untersuchten Technologien lassen sich den Feldern Biotechnologie, Nanotechnologie, Umwelttechnologie und Sensorik zuordnen. Zentrales Ergebnis der Arbeit ist ein entsprechend der Erfahrungen in den Unternehmen angepasster Ansatz für die Vorausschau und Planung neuer Technologiepfade. Dieser Ansatz ist in Abhängigkeit von Unternehmens- und Technologiecharakteristika für die weitere Anwendung konkretisiert. Dabei finden die zu beteiligenden Organisationseinheiten, zu betrachtende Einflussfaktoren sowie anwendbare Methoden besondere Berücksichtigung. Die Arbeit richtet sich an Personen in Führungspositionen im Bereich des strategischen Technologiemanagements sowie der Forschung und Entwicklung in Unternehmen, die Strategien für neu aufkommende Technologien entwickeln. Weiterhin sind die Ergebnisse der Arbeit für Wissenschaftler auf dem Gebiet der Methoden zur Vorausschau und Strategieentwicklung für neue Technologien von Interesse.

Web Service Composition Systems for the Web Service Challenge - A Detailed Review

This report gives a detailed discussion on the system, algorithms, and techniques that we have applied in order to solve the Web Service Challenges (WSC) of the years 2006 and 2007. These international contests are focused on semantic web service composition. In each challenge of the contests, a repository of web services is given. The input and output parameters of the services in the repository are annotated with semantic concepts. A query to a semantic composition engine contains a set of available input concepts and a set of wanted output concepts. In order to employ an offered service for a requested role, the concepts of the input parameters of the offered operations must be more general than requested (contravariance). In contrast, the concepts of the output parameters of the offered service must be more specific than requested (covariance). The engine should respond to a query by providing a valid composition as fast as possible. We discuss three different methods for web service composition: an uninformed search in form of an IDDFS algorithm, a greedy informed search based on heuristic functions, and a multi-objective genetic algorithm.

Applicability of Emergence Engineering to Distributed Systems Scenarios

Genetic Programming can be effectively used to create emergent behavior for a group of autonomous agents. In the process we call Offline Emergence Engineering, the behavior is at first bred in a Genetic Programming environment and then deployed to the agents in the real environment. In this article we shortly describe our approach, introduce an extended behavioral rule syntax, and discuss the impact of the expressiveness of the behavioral description to the generation success, using two scenarios in comparison: the election problem and the distributed critical section problem. We evaluate the results, formulating criteria for the applicability of our approach.

An introduction to ordinary differential equations by computer algebra-systems

We report on an elementary course in ordinary differential equations (odes) for students in engineering sciences. The course is also intended to become a self-study package for odes and is is based on several interactive computer lessons using REDUCE and MATHEMATICA . The aim of the course is not to do Computer Algebra (CA) by example or to use it for doing classroom examples. The aim ist to teach and to learn mathematics by using CA-systems.

Nachhaltige Energie für ländliche Entwicklung in dem Sub-Sahara Afrika: interdisziplinäre Herangehensweise und organisatorische Herausforderung

Angesichts der Geschichte der Entwicklungspolitik, ist diese Arbeit darauf ausgerichtet, einige Beobachtungen in Bezug auf die so genannte Entwicklung hervorzuheben; insbesondere auf die andauernde prekäre Situation und Armut in ländlichen afrikanischen Gebieten. Armut ist nach Amartya SEN – weiter präzisiert von J.L. Dubois – die Deprivation von „Fähigkeiten“, die Individuen und lokale Gemeinschaften zu ausgeschlossenen und vergessenen Akteuren des Systems machen. Das nennt Paulo Freire, das Menschen zu „Objekten“ gemacht werden. Es rechtfertigt die starke Annahme, die in dieser Studie getroffen wird, dass vielmehr die Menschen als „Subjekte“ ihrer Veränderung und Entwicklung im Mittelpunkt stehen. Die Arbeit zeigt und erklärt in historischer Chronologie, wie die Entwicklungspolitiken und unterschiedliche Beteiligte auf allen Ebenen diese Situation verursachen. Trotz alledem bleiben die Individuen und lokalen Gemeinschaften, die in Symbiose mit ihrer natürlichen Umwelt leben, die reich an verschiedenen Ressourcen und Potentialen ist, als Reaktion darauf und gleichzeitig als Überlebensstrategie zutiefst verbunden mit dem, was sie vor Ort haben, womit sie eine tiefere und intensive Beziehung besitzen, wenn man von ihrer Geschichte, ihrer Kultur und der Handlungslogik ausgeht. Für externe Akteure, die sie über das vorhandene System dominieren und beeinflussen bleiben sie „Objekte“, aber in der Vielzahl ihrer endogenen Initiativen, zeigen sie die Fähigkeit und Substanz, die beweisen, dass sie auf ihrer Ebene das eigentliche Subjekt sind, die dynamischen Akteure. Aber isolierte Initiativen auf spezifische reale Bedürfnisse bei gleichzeitiger Dominierung durch das System mit seiner Marktlogik, führt dies langfristig nur zu dem Zirkulus Vitiosus der Armut. Daher ist eine ganzheitliche Sicht entscheidend für nachhaltige Entwicklung und für die notwendige Veränderung. Es geht nicht nur um die Veränderung des Systems und die Wahl politischer Maßnahmen, sondern genau genommen um das Verhalten der Akteure auf allen Ebenen und die Art der Beziehungen zwischen ihnen allen. Es ist eine Frage des erneuten Überdenkens des Entwicklungspfades, der andere Logik, Visionen, Interessen und Strategien aller Beteiligten, unserer so genannten Akteure einschließt. Ob dies von endogenen Initiativen oder neuen gemeinsamen Projekten ausgeht: man wird in einen Prozess kollektiven Lernens eintreten, den Paul Singer und Clarita Müller-Plantenberg erläutern und entwickeln in dem Konzept der Inkubation und Solidarischen Ökonomie, die Eigeninitiative, Selbstbestimmung und Selbstverwaltung von lokalen Gemeinschaften und die Öffnung für eine Neu-Konzeptualisierung und Institutionalisierung einschließt. So ein Prozess ist nur mit einem interdisziplinären Rahmen möglich. Dieser Rahmen soll auf einer zusätzlicher Kommunikation zwischen den Akteuren und Sozialwissenschaften beruhen und mit jenen, die auf dem Feld der Technologie arbeiten. So können dann technische „Experten“ angesichts eines technischen Projektfehlers, der aufgrund von bestimmten sozialen und kulturellen Realitäten zustande kam sagen, „es ist kein Scheitern ; es war ein Schritt innerhalb eines Lernprozesse der in die technischen Projekte und Studien einbezogen werden muss“. Wir haben das Energiethema gewählt; und insbesondere, Energie für eine nachhaltige ländliche Entwicklung in Subsahara-Afrika, um den Weg von der Theorie in die Praxis zu illustrieren und experimentell auszuprobieren, den Weg von den Beobachtungen zu der Veränderung, wobei Fragen, Annahmen, Strategien und konkrete Aktionen für den Wandel behandelt werden. Wir nennen unseren experimentellen Weg: DRIEE, das heißt auf Deutsch Ländliche Entwicklung und Inkubation von Energieunternehmen. Dabei gehen wir davon aus, dass: - Energie im Allgemeinen auf der internationalen Ebene fast gleichbedeutend mit Elektrizität ist. Heute bestehen die wichtigsten Bedürfnisse nach Energie dort wo die agro-pastorale Produktion, das Kochen, die Nahrungsmittelkonservierung und Verarbeitung …etc. stattfindet. - Diese ländliche Bevölkerung zu etwa 80% der nationalen Wirtschaft ausmacht. Dass sie gleichzeitig aber nur zu weniger als 5% der Energieproduktion Zugang hat, was oft auf Licht reduziert ist und nicht einmal ihrer Produktion zugute kommen kann. - Die Projekte für Energie und Elektrizität vor allem auf die Technologischen Fragen konzentriert sind und weniger auf die Bedürfnisse. Fast die Gesamtheit der Fonds für Energie wird in Bezug auf die Investitionen Infrastruktur der Produktion und Verteilung durch die konventionellen zentralisierten Netze geplant. Angesichts dieser Analysen gehen die in dieser Arbeit vorgenommenen Studien in Gambia und Kamerun von Bestandsaufnahmen und / oder beschreibenden regionalen Analysen aus: - von Bedürfnissen, von Praktiken und lokalen Initiativen von Fragen der Energie, für einzelne Professionen, Haushalte, Gruppen, spezifische Gruppen, wie Frauen, ländliche Gemeinden mit ihren spezifischen Charakteristika. - Von Potentialen: natürliche lokale Energieressourcen, soziokulturelle Ressourcen – so z.B. die empirisch feststellbaren menschliche Ressourcen wie endogenes Wissen und praktische organisatorische Fähigkeiten gegenüber den Problemen der Energie. Dieser experimentelle Schritt von Handlungsforschung (DRIEE) in Kamerun führte zu der Gründung einer Organisation, über die und mit der wir die Logik der Inkubation und Solidarischen Ökonomie einführen. Das ist FERDEDSI, das heißt auf Deutsch „Forum für Erneuerbare Energie – Nachhaltige Entwicklung und Internationale Solidarität“. Zunächst war dies eine Energiegenossenschaft und dann (im Prozess) wurde es zu einer institutionellen Nische von mehreren Mikro Initiativen in ländlichen Gebieten. FERDEDSI ist ein Prozess der Inkubation und ein Inkubator ist also gleichzeitig ein inkubiertes Energieunternehmen aber auch ein Inkubator für lokale Organisationen. Die ersten Aktionen finden in den Departments von Noun und Ménoua in der westlichen Provinz von Kamerun statt. Während der Forschungsperiode findet akademische Austausch statt (Nord-Süd und Süd-Süd), diese ist dabei zu formalen Partnerschaften zu werden, nicht nur zwischen Universitäten sondern genauer lokale Organisationen und Universitäten. Dieser letzte Typ von Partnerschaften, die die solidarische Ökonomie ausmachen ist auch eine Innovation des Prozesses für die afrikanischen Fälle, die dem Beispiel dessen, was in Lateinamerika geschieht, folgen. So kommt es zu gegenseitiger sinnvoller Ausbildung in den internationalen Arbeitsgruppen und Seminaren der Universität.

On Globally Deterministic CD-Systems of Stateless R-Automata with Window Size One

It is known that cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 accept a class of semi-linear languages that properly includes all rational trace languages. Although the component automata of such a CD-system are all deterministic, in general the CD-system itself is not, as in each of its computations, the initial component and the successor components are still chosen nondeterministically. Here we study CD-systems of stateless deterministic restarting automata with window size 1 that are themselves completely deterministic. In fact, we consider two such types of CD-systems, the strictly deterministic systems and the globally deterministic systems.