On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

On the Descriptional Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.

Degrees of Free Word-Order and Freely Rewriting Restarting Automata

In natural languages with a high degree of word-order freedom syntactic phenomena like dependencies (subordinations) or valencies do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: 1. the degree of j-monotonicity, and 2. the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

Framework for middleware executed on mobile devices

Die ubiquitäre Datenverarbeitung ist ein attraktives Forschungsgebiet des vergangenen und aktuellen Jahrzehnts. Es handelt von unaufdringlicher Unterstützung von Menschen in ihren alltäglichen Aufgaben durch Rechner. Diese Unterstützung wird durch die Allgegenwärtigkeit von Rechnern ermöglicht die sich spontan zu verteilten Kommunikationsnetzwerken zusammen finden, um Informationen auszutauschen und zu verarbeiten. Umgebende Intelligenz ist eine Anwendung der ubiquitären Datenverarbeitung und eine strategische Forschungsrichtung der Information Society Technology der Europäischen Union. Das Ziel der umbebenden Intelligenz ist komfortableres und sichereres Leben. Verteilte Kommunikationsnetzwerke für die ubiquitäre Datenverarbeitung charakterisieren sich durch Heterogenität der verwendeten Rechner. Diese reichen von Kleinstrechnern, eingebettet in Gegenstände des täglichen Gebrauchs, bis hin zu leistungsfähigen Großrechnern. Die Rechner verbinden sich spontan über kabellose Netzwerktechnologien wie wireless local area networks (WLAN), Bluetooth, oder UMTS. Die Heterogenität verkompliziert die Entwicklung und den Aufbau von verteilten Kommunikationsnetzwerken. Middleware ist eine Software Technologie um Komplexität durch Abstraktion zu einer homogenen Schicht zu reduzieren. Middleware bietet eine einheitliche Sicht auf die durch sie abstrahierten Ressourcen, Funktionalitäten, und Rechner. Verteilte Kommunikationsnetzwerke für die ubiquitäre Datenverarbeitung sind durch die spontane Verbindung von Rechnern gekennzeichnet. Klassische Middleware geht davon aus, dass Rechner dauerhaft miteinander in Kommunikationsbeziehungen stehen. Das Konzept der dienstorienterten Architektur ermöglicht die Entwicklung von Middleware die auch spontane Verbindungen zwischen Rechnern erlaubt. Die Funktionalität von Middleware ist dabei durch Dienste realisiert, die unabhängige Software-Einheiten darstellen. Das Wireless World Research Forum beschreibt Dienste die zukünftige Middleware beinhalten sollte. Diese Dienste werden von einer Ausführungsumgebung beherbergt. Jedoch gibt es noch keine Definitionen wie sich eine solche Ausführungsumgebung ausprägen und welchen Funktionsumfang sie haben muss. Diese Arbeit trägt zu Aspekten der Middleware-Entwicklung für verteilte Kommunikationsnetzwerke in der ubiquitären Datenverarbeitung bei. Der Schwerpunkt liegt auf Middleware und Grundlagentechnologien. Die Beiträge liegen als Konzepte und Ideen für die Entwicklung von Middleware vor. Sie decken die Bereiche Dienstfindung, Dienstaktualisierung, sowie Verträge zwischen Diensten ab. Sie sind in einem Rahmenwerk bereit gestellt, welches auf die Entwicklung von Middleware optimiert ist. Dieses Rahmenwerk, Framework for Applications in Mobile Environments (FAME²) genannt, beinhaltet Richtlinien, eine Definition einer Ausführungsumgebung, sowie Unterstützung für verschiedene Zugriffskontrollmechanismen um Middleware vor unerlaubter Benutzung zu schützen. Das Leistungsspektrum der Ausführungsumgebung von FAME² umfasst: • minimale Ressourcenbenutzung, um auch auf Rechnern mit wenigen Ressourcen, wie z.B. Mobiltelefone und Kleinstrechnern, nutzbar zu sein • Unterstützung für die Anpassung von Middleware durch Änderung der enthaltenen Dienste während die Middleware ausgeführt wird • eine offene Schnittstelle um praktisch jede existierende Lösung für das Finden von Diensten zu verwenden • und eine Möglichkeit der Aktualisierung von Diensten zu deren Laufzeit um damit Fehlerbereinigende, optimierende, und anpassende Wartungsarbeiten an Diensten durchführen zu können Eine begleitende Arbeit ist das Extensible Constraint Framework (ECF), welches Design by Contract (DbC) im Rahmen von FAME² nutzbar macht. DbC ist eine Technologie um Verträge zwischen Diensten zu formulieren und damit die Qualität von Software zu erhöhen. ECF erlaubt das aushandeln sowie die Optimierung von solchen Verträgen.

Organic potatoes for processing

Drei Feldversuche auf zwei Standorten (DFH: 51°4, 9°4’, BEL: 52°2’, 8°08’) wurden in den Jahren 2002 bis 2004 durchgeführt, um den Einfluss der Vorfrucht, des Vorkeimens, der N- und K-Düngung und der Sorte auf Nährstoffverfügbarkeit, Gesamt- und sortierte Knollenerträge sowie die Qualität von Kartoffeln und deren Eignung für die industrielle Verarbeitung zu Pommes frites und Chips zu untersuchen. Bestimmt wurden die N- und K-Verfügbarkeit im Boden, die N- und K-Aufnahme von Kraut und Knollen, gesamte Frisch- und Trockenmasseerträge, sortierte Frischmasseerträge für die Verarbeitung, sowie die Gehalte der Knollen an Trockensubstanz und reduzierenden Zuckern. In einer sensorischen Prüfung wurden Qualitätsparameter von Pommes frites (Aussehen/Farbe, Textur und Geschmack/Geruch) bewertet, die gewichtet in einen Qualitätsindex eingingen. Die Qualität der Chips wurde maschinell durch den L-Wert (Helligkeit) des Produktes quantifiziert. Der Gehalt des Bodens an mineralisiertem Nitrat-Stickstoff hing von der Vorfrucht und dem Jahr ab. Nach Erbsen wurden zum Auflaufen der Kartoffeln in den Versuchsjahren 2003 und 2004 (187 und 132 kg NO3-N ha-1) die höchsten NO3-N-Werte in 0-60 cm Boden gemessen verglichen mit Kleegras (169 bzw. 108 kg NO3-N ha-1 oder Getreide (112 kg bzw. 97 kg NO3-N ha-1), obgleich die Differenz nicht in allen Fällen signifikant war. Entsprechend wurden nach Erbsen die höchsten Knollen-Frischmasseerträge (414 und 308 dt ha-1) geerntet. Dasselbe galt für die Trockenmasserträge, was belegt, dass der Trockensubstanzgehalt der Knollen bei verbesserter N-Versorgung nicht im selben Maße sinkt, wie der Frischmasseertrag steigt. Das Vorkeimen der Pflanzknollen führte zu einer rascheren phänologischen Entwicklung im Jugendstadium der Pflanze, beschleunigter Trockenmassebildung des Krautes und einer früheren Einlagerung von Assimilaten vom Kraut in die Knollen. Obwohl die positive Wirkung des Vorkeimens auf den Gesamtertrag bis Ende Juli (+ 26 in 2003 bzw. 34 dt ha-1 in 2004) im Jahr ohne Krautfäuleepidemie von den nicht vorgekeimten Varianten bis zur Endernte im September kompensiert wurde, konnte in diesem Jahr durch Vorkeimen dennoch ein erhöhter Ertragsanteil (+ 12%) der besonders nachgefragten Übergrößen (>50 mm für Pommes frites) erzielt werden. Die durchschnittliche Knollenmasse reagierte positiv auf Vorkeimen (+ 5,4 g), Sortenwahl (Sorte Agria) und ein erhöhtes N-Angebot (Leguminosenvorfrucht). Generell wurde deutlich, dass die Knollengesamterträge unter den Bedingungen des Ökologischen Landbaus (geringe bis mittlere Nährstoffversorgung, verkürzte Vegetationsdauer) sehr stark vom Anbaujahr abhängen. Die Ergebnisse belegen jedoch, dass organisch-mineralische N-K-Düngung den sortierten Ertrag an Knollen für die Verarbeitung signifikant erhöht: Höchste Gesamt- und sortierte Knollenfrischmasseerträge wurden nach kombinierter N (Horngrieß) und mineralischer K- (Kaliumsulfat) Gabe erzielt (348 dt ha-1 im Durchschnitt von 2002-2004). Im Gegensatz dazu kann eine Wirkung von Stallmist auf den Ertrag im Jahr der Ausbringung nicht unbedingt erwartet werden. Steigende Erträge nach Stallmistdüngung wurden lediglich in einem von drei Versuchsjahren (+58 dt ha-1) festgestellt und ließen sich eher auf eine K- als eine N-Wirkung zurückführen. Die Ergebnisse belegen, dass die Sortenwahl eine entscheidende Rolle spielt, wenn die Kartoffeln für die industrielle Verarbeitung zu den oben genannten Produkten angebaut werden. Insgesamt kann festgestellt werden, dass Kartoffelknollen aus ökologischen Anbauverfahren ausreichend hohe Trockensubstanzgehalte aufweisen, um für die Verarbeitung zu Pommes frites (>19%) geeignet zu sein und ohne dass dadurch die Konsistenz des Endproduktes gefährdet würde. Der Trockensubstanzgehalt der Referenzsorte für Chips, „Marlen“, unterschritt das in der Literatur geforderte Minimum für Chips von 23% lediglich, wenn die kombinierte Horngrieß-Kaliumsulfatdüngung zur Anwendung kam. Die Trockensubstanzgehalte der Knollen konnten durch Vorkeimen signifikant gesteigert werden und der Effekt war besonders groß (+1.2% absolut) in dem Jahr mit frühem Auftreten der Krautfäule (Phytophthora infestans), d.h. verkürzter Vegetationszeit. Die Knollen-Trockensubstanzgehalte waren in zwei von drei Experimenten nach Lagerung höher (+0.4 und 0.5% absolut) als noch zur Ernte. Sorten der sehr frühen und frühen Reifegruppe wiesen den größten relativen Anstieg der Gehalte an reduzierenden Zuckern (Glukose und Fruktose) während der Lagerung auf. Den mittelfrühen Sorten „Agria“ und „Marena“ hingegen kann aufgrund des von ihnen erreichten höchsten Qualitätsstandards (Pommes frites) zur Ernte eine sehr gute Eignung für die Bedingungen des Ökologischen Landbaus unterstellt werden. Die durchgehend beste Chipseignung wies die mittelfrühe Referenzsorte „Marlen“ auf. Insgesamt konnte nachgewiesen werden, dass durch gezielte Sortenwahl der Trockensubstanzgehalt und die Konzentration reduzierender Zucker, sowie die Qualität der Endprodukte (Pommes frites und Chips) gezielt beeinflusst werden kann. Im Gegensatz dazu haben acker- und pflanzenbauliche Maßnahmen wie Düngung, Wahl der Vorfrucht und Vorkeimen der Pflanzknollen einen eher geringen Einfluss. Dementsprechend sollte der Landwirt versuchen, durch die Wahl der Sorte den hohen Anforderungen der Industrie an die Rohware gerecht zu werden.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

Virtual Radio Engine

Software Defined Radio (SDR) hardware platforms use parallel architectures. Current concepts of developing applications (such as WLAN) for these platforms are complex, because developers describe an application with hardware-specifics that are relevant to parallelism such as mapping and scheduling. To reduce this complexity, we have developed a new programming approach for SDR applications, called Virtual Radio Engine (VRE). VRE defines a language for describing applications, and a tool chain that consists of a compiler kernel and other tools (such as a code generator) to generate executables. The thesis presents this concept, as well as describes the language and the compiler kernel that have been developed by the author. The language is hardware-independent, i.e., developers describe tasks and dependencies between them. The compiler kernel performs automatic parallelization, i.e., it is capable of transforming a hardware-independent program into a hardware-specific program by solving hardware-specifics, in particular mapping, scheduling and synchronizations. Thus, VRE simplifies programming tasks as developers do not solve hardware-specifics manually.

On-line analytical processing with conceptual information systems

A conceptual information system consists of a database together with conceptual hierarchies. The management system TOSCANA visualizes arbitrary combinations of conceptual hierarchies by nested line diagrams and allows an on-line interaction with a database to analyze data conceptually. The paper describes the conception of conceptual information systems and discusses the use of their visualization techniques for on-line analytical processing (OLAP).

Conceptual knowledge discovery with frequent concept lattices

Knowledge discovery support environments include beside classical data analysis tools also data mining tools. For supporting both kinds of tools, a unified knowledge representation is needed. We show that concept lattices which are used as knowledge representation in Conceptual Information Systems can also be used for structuring the results of mining association rules. Vice versa, we use ideas of association rules for reducing the complexity of the visualization of Conceptual Information Systems.

Conceptual knowledge processing with formal concept analysis and ontologies

Among many other knowledge representations formalisms, Ontologies and Formal Concept Analysis (FCA) aim at modeling ‘concepts’. We discuss how these two formalisms may complement another from an application point of view. In particular, we will see how FCA can be used to support Ontology Engineering, and how ontologies can be exploited in FCA applications. The interplay of FCA and ontologies is studied along the life cycle of an ontology: (i) FCA can support the building of the ontology as a learning technique. (ii) The established ontology can be analyzed and navigated by using techniques of FCA. (iii) Last but not least, the ontology may be used to improve an FCA application.

A finite state model for on-line analytical processing in triadic contexts

About ten years ago, triadic contexts were presented by Lehmann and Wille as an extension of Formal Concept Analysis. However, they have rarely been used up to now, which may be due to the rather complex structure of the resulting diagrams. In this paper, we go one step back and discuss how traditional line diagrams of standard (dyadic) concept lattices can be used for exploring and navigating triadic data. Our approach is inspired by the slice & dice paradigm of On-Line-Analytical Processing (OLAP). We recall the basic ideas of OLAP, and show how they may be transferred to triadic contexts. For modeling the navigation patterns a user might follow, we use the formalisms of finite state machines. In order to present the benefits of our model, we show how it can be used for navigating the IT Baseline Protection Manual of the German Federal Office for Information Security.

User Profile Management and Selection in Context-Aware Service Platforms for Networks Beyond 3G

In recent years, progress in the area of mobile telecommunications has changed our way of life, in the private as well as the business domain. Mobile and wireless networks have ever increasing bit rates, mobile network operators provide more and more services, and at the same time costs for the usage of mobile services and bit rates are decreasing. However, mobile services today still lack functions that seamlessly integrate into users’ everyday life. That is, service attributes such as context-awareness and personalisation are often either proprietary, limited or not available at all. In order to overcome this deficiency, telecommunications companies are heavily engaged in the research and development of service platforms for networks beyond 3G for the provisioning of innovative mobile services. These service platforms are to support such service attributes. Service platforms are to provide basic service-independent functions such as billing, identity management, context management, user profile management, etc. Instead of developing own solutions, developers of end-user services such as innovative messaging services or location-based services can utilise the platform-side functions for their own purposes. In doing so, the platform-side support for such functions takes away complexity, development time and development costs from service developers. Context-awareness and personalisation are two of the most important aspects of service platforms in telecommunications environments. The combination of context-awareness and personalisation features can also be described as situation-dependent personalisation of services. The support for this feature requires several processing steps. The focus of this doctoral thesis is on the processing step, in which the user’s current context is matched against situation-dependent user preferences to find the matching user preferences for the current user’s situation. However, to achieve this, a user profile management system and corresponding functionality is required. These parts are also covered by this thesis. Altogether, this thesis provides the following contributions: The first part of the contribution is mainly architecture-oriented. First and foremost, we provide a user profile management system that addresses the specific requirements of service platforms in telecommunications environments. In particular, the user profile management system has to deal with situation-specific user preferences and with user information for various services. In order to structure the user information, we also propose a user profile structure and the corresponding user profile ontology as part of an ontology infrastructure in a service platform. The second part of the contribution is the selection mechanism for finding matching situation-dependent user preferences for the personalisation of services. This functionality is provided as a sub-module of the user profile management system. Contrary to existing solutions, our selection mechanism is based on ontology reasoning. This mechanism is evaluated in terms of runtime performance and in terms of supported functionality compared to other approaches. The results of the evaluation show the benefits and the drawbacks of ontology modelling and ontology reasoning in practical applications.