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.

Composition and stability of organic matter fractions in soils under different land use regimes

Soil organic matter (SOM) vitally impacts all soil functions and plays a key role in the global carbon (C) cycle. More than 70% of the terrestric C stocks that participate in the active C cycle are stored in the soil. Therefore, quantitative knowledge of the rates of C incorporation into SOM fractions of different residence time is crucial to understand and predict the sequestration and stabilization of soil organic carbon (SOC). Consequently, there is a need of fractionation procedures that are capable of isolating functionally SOM fractions, i.e. fractions that are defined by their stability. The literature generally refers to three main mechanisms of SOM stabilization: protection of SOM from decomposition by (i) its structural composition, i.e. recalcitrance, (ii) spatial inaccessibility and/or (iii) interaction with soil minerals and metal ions. One of the difficulties in developing fractionation procedures for the isolation of functional SOM fractions is the marked heterogeneity of the soil environment with its various stabilization mechanisms – often several mechanisms operating simultaneously – in soils and soil horizons of different texture and mineralogy. The overall objective of the present thesis was to evaluate present fractionation techniques and to get a better understanding of the factors of SOM sequestration and stabilization. The first part of this study is attended to the structural composition of SOM. Using 13C cross-polarization magic-angle spinning (CPMAS) nuclear magnetic resonance (NMR) spectroscopy, (i) the effect of land use on SOM composition was investigated and (ii) examined whether SOM composition contributes to the different stability of SOM in density and aggregate fractions. The second part of the present work deals with the mineral-associated SOM fraction. The aim was (iii) to evaluate the suitability of chemical fractionation procedures used in the literature for the isolation of stable SOM pools (stepwise hydrolysis, treatments using oxidizing agents like Na2S2O8, H2O2, and NaOCl as well as demineralization of the residue obtained by the NaOCl treatment using HF (NaOCl+HF)) by pool sizes, 13C and 14C data. Further, (iv) the isolated SOM fractions were compared to the inert organic matter (IOM) pool obtained for the investigated soils using the Rothamsted Carbon Model and isotope data in order to see whether the tested chemical fractionation methods produce SOM fractions capable to represent this pool. Besides chemical fractionation, (v) the suitability of thermal oxidation at different temperatures for obtaining stable SOC pools was evaluated. Finally, (vi) the short-term aggregate dynamics and the factors that impact macroaggregate formation and C stabilization were investigated by means of an incubation study using treatments with and without application of 15N labeled maize straw of different degradability (leaves and coarse roots). All treatments were conducted with and without the addition of fungicide. Two study sites with different soil properties and land managements were chosen for these investigations. The first one, located at Rotthalmünster, is a Stagnic Luvisol (silty loam) under different land use regimes. The Ah horizons of a spruce forest and continuous grassland and the Ap and E horizons of two plots with arable crops (continuous maize and wheat cropping) were examined. The soil of the second study site, located at Halle, is a Haplic Phaeozem (loamy sand) where the Ap horizons of two plots with arable crops (continuous maize and rye cropping) were investigated. Both study sites had a C3-/C4-vegetational change on the maize plot for the purpose of tracing the incorporation of the younger, maize-derived C into different SOM fractions and the calculation of apparent C turnover times of these. The Halle site is located near a train station and industrial areas, which caused a contamination with high amounts of fossil C. The investigation of aggregate and density fractions by 13C CPMAS NMR spectroscopy revealed that density fractionation isolated SOM fractions of different composition. The consumption of a considerable part (10–20%) of the easily available O-alkyl-C and the selective preservation of the more recalcitrant alkyl-C when passing from litter to the different particulate organic matter (POM) fractions suggest that density fractionation was able to isolate SOM fractions with different degrees of decomposition. The spectra of the aggregate fractions resembled those of the mineral-associated SOM fraction obtained by density fractionation and no considerable differences were observed between aggregate size classes. Comparison of plant litter, density and aggregate size fractions from soil under different land use showed that the type of land use markedly influenced the composition of SOM. While SOM of the acid forest soil was characterized by a large content (> 50%) of POM, which contained high amounts of spruce-litter derived alkyl-C, the organic matter in the biologically more active grassland and arable soils was dominated by mineral-associated SOM (> 95%). This SOM fraction comprised greater proportions of aryl- and carbonyl-C and is considered to contain a higher amount of microbially-derived organic substances. Land use can alter both, structure and stability of SOM fractions. All applied chemical treatments induced considerable SOC losses (> 70–95% of mineral-associated SOM) in the investigated soils. The proportion of residual C after chemical fractionation was largest in the arable Ap and E horizons and increased with decreasing C content in the initial SOC after stepwise hydrolysis as well as after the oxidative treatments with H2O2 and Na2S2O8. This can be expected for a functional stable pool of SOM, because it is assumed that the more easily available part of SOC is consumed first if C inputs decrease. All chemical treatments led to a preferential loss of the younger, maize-derived SOC, but this was most pronounced after the treatments with Na2S2O8 and H2O2. After all chemical fractionations, the mean 14C ages of SOC were higher than in the mineral-associated SOM fraction for both study sites and increased in the order: NaOCl < NaOCl+HF ≤ stepwise hydrolysis << H2O2 ≈ Na2S2O8. The results suggest that all treatments were capable of isolating a more stable SOM fraction, but the treatments with H2O2 and Na2S2O8 were the most efficient ones. However, none of the chemical fractionation methods was able to fit the IOM pool calculated using the Rothamsted Carbon Model and isotope data. In the evaluation of thermal oxidation for obtaining stable C fractions, SOC losses increased with temperature from 24–48% (200°C) to 100% (500°C). In the Halle maize Ap horizon, losses of the young, maize-derived C were considerably higher than losses of the older C3-derived C, leading to an increase in the apparent C turnover time from 220 years in mineral-associated SOC to 1158 years after thermal oxidation at 300°C. Most likely, the preferential loss of maize-derived C in the Halle soil was caused by the presence of the high amounts of fossil C mentioned above, which make up a relatively large thermally stable C3-C pool in this soil. This agrees with lower overall SOC losses for the Halle Ap horizon compared to the Rotthalmünster Ap horizon. In the Rotthalmünster soil only slightly more maize-derived than C3-derived SOC was removed by thermal oxidation. Apparent C turnover times increased slightly from 58 years in mineral-associated SOC to 77 years after thermal oxidation at 300°C in the Rotthalmünster Ap and from 151 to 247 years in the Rotthalmünster E horizon. This led to the conclusion that thermal oxidation of SOM was not capable of isolating SOM fractions of considerably higher stability. The incubation experiment showed that macroaggregates develop rapidly after the addition of easily available plant residues. Within the first four weeks of incubation, the maximum aggregation was reached in all treatments without addition of fungicide. The formation of water-stable macroaggregates was related to the size of the microbial biomass pool and its activity. Furthermore, fungi were found to be crucial for the development of soil macroaggregates as the formation of water-stable macroaggregates was significantly delayed in the fungicide treated soils. The C concentration in the obtained aggregate fractions decreased with decreasing aggregate size class, which is in line with the aggregate hierarchy postulated by several authors for soils with SOM as the major binding agent. Macroaggregation involved incorporation of large amounts maize-derived organic matter, but macroaggregates did not play the most important role in the stabilization of maize-derived SOM, because of their relatively low amount (less than 10% of the soil mass). Furthermore, the maize-derived organic matter was quickly incorporated into all aggregate size classes. The microaggregate fraction stored the largest quantities of maize-derived C and N – up to 70% of the residual maize-C and -N were stored in this fraction.

The Degree of Word-Expansion of Lexicalized RRWW-Automata

Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

CEM - visualization and discovery in Email

This paper presents a lattice-based visual metaphor for knowledge discovery in electronic mail. It allows a user to navigate email using a visual lattice metaphor rather than a tree structure. By using such a conceptual multi-hierarchy, the content and shape of the lattice can be varied to accommodate any number of queries against the email collection. The system provides more flexibility in retrieving stored emails and can be generalised to any electronic documents. The paper presents the underlying mathematical structures, and a number of examples of the lattice and multi-hierarchy working with a prototypical email collection.

CEM - a conceptual Email manager

CEM is an email management system which stores its email in a concept lattice rather than in the usual tree structure. By using such a conceptual multi-hierarchy, the system provides more flexibility in retrieving stored emails. The paper presents the underlying mathematical structures, discusses requirements for their maintenance and presents their implementation.

Relations and Transductions Realized by Restarting Automata

Gegenstand der vorliegenden Arbeit ist die Analyse verschiedener Formalismen zur Berechnung binärer Wortrelationen. Dabei ist die Grundlage aller hier ausgeführten Betrachtungen das Modell der Restart-Automaten, welches 1995 von Jancar et. al. eingeführt wurde. Zum einen wird das bereits für Restart-Automaten bekannte Konzept der input/output- und proper-Relationen weiterführend untersucht, sowie auf Systeme von zwei parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (PC-Systeme) erweitert. Zum anderen wird eine Variante der Restart-Automaten eingeführt, die sich an klassischen Automatenmodellen zur Berechnung von Relationen orientiert. Mit Hilfe dieser Mechanismen kann gezeigt werden, dass einige Klassen, die durch input/output- und proper-Relationen von Restart Automaten definiert werden, mit den traditionellen Relationsklassen der Rationalen Relationen und der Pushdown-Relationen übereinstimmen. Weiterhin stellt sich heraus, dass das Konzept der parallel kommunizierenden Automaten äußerst mächtig ist, da bereits die Klasse der proper-Relationen von monotonen PC-Systemen alle berechenbaren Relationen umfasst. Der Haupteil der Arbeit beschäftigt sich mit den so genannten Restart-Transducern, welche um eine Ausgabefunktion erweiterte Restart-Automaten sind. Es zeigt sich, dass sich insbesondere dieses Modell mit seinen verschiedenen Erweiterungen und Einschränkungen dazu eignet, eine umfassende Hierarchie von Relationsklassen zu etablieren. In erster Linie seien hier die verschiedenen Typen von monotonen Restart-Transducern erwähnt, mit deren Hilfe viele interessante neue und bekannte Relationsklassen innerhalb der längenbeschränkten Pushdown-Relationen charakterisiert werden. Abschließend wird, im Kontrast zu den vorhergehenden Modellen, das nicht auf Restart-Automaten basierende Konzept des Übersetzens durch Beobachtung ("Transducing by Observing") zur Relationsberechnung eingeführt. Dieser, den Restart-Transducern nicht unähnliche Mechanismus, wird im weitesten Sinne dazu genutzt, einen anderen Blickwinkel auf die von Restart-Transducern definierten Relationen einzunehmen, sowie eine obere Schranke für die Berechnungskraft der Restart-Transducer zu gewinnen.

Understanding Recreational Services of Urban Riverfront Space for Planning Purposes

In the process of urbanization, natural and semi-natural landscapes are increasingly cherished as open space and recreational resource. Urban rivers are part of this kind of resource and thus play an important role in managing urban resilience and health. Employing the example of Tianjin, this doctoral dissertation research aims at learning to understand how to plan and design for the interface zones between urban water courses and for the land areas adjacent to such water courses. This research also aims at learning how to link waterfront space with other urban space in order to make a recreational space system for the benefit of people. Five questions of this dissertation are: 1) what is the role of rivers in spatial and open space planning? 2) What are the human needs regarding outdoor open space? 3) How do river and water front spatial structures affect people's recreational activities? 4) How to define the recreational service of urban river and waterfront open space? 5) How might answering these question change planning and design of urban open space? Quantitative and qualitative empirical approaches were combined in this study for which literature review and theoretical explorations provide the basis. Empirical investigations were conducted in the city of Tianjin. The quantitative approach includes conducting 267 quantitative interviews, and the qualitative approach includes carrying out field observations and mappings. GIS served to support analysis and visualization of empirical information that was generated through this study. By responding to the five research questions, findings and lessons include the following: 1) In the course of time rivers have gained importance in all levels and scales of spatial planning and decision making. Regarding the development of ecological networks, mainly at national scale, rivers are considered significant linear elements. Regarding regional and comprehensive development, river basins and watersheds are often considered as the structural link for strategic ecological, economic, social and recreational planning. For purposes of urban planning, particularly regarding recreational services in cities, the distribution of urban open spaces often follows the structure of river systems. 2) For the purpose of classifying human recreational needs that relate to outdoor open space Maslow's hierarchy of human needs serves as theoretical basis. The classes include geographical, safety, physiological, social and aesthetic need. These classes serve as references while analyzing river and waterfront open space and other kinds of open space. 3) Regarding the question how river and waterfront spatial structures might affect people's recreational activities, eight different landscape units were identified and compared in the case study area. Considering the thermal conditions of Tianjin, one of these landscape units was identified as affording the optimal spatial arrangement which mostly meets recreational needs. The size and the shape of open space, and the plants present in an open space have been observed as being most relevant regarding recreational activities. 4) Regarding the recreational service of urban river and waterfront open space the results of this research suggest that the recreational service is felt less intensively as the distances between water 183 front and open space user’s places of residence are increasing. As a method for estimating this ‘Service Distance Effect’ the following formula may be used: Y = a*ebx. In this equation Y means the ‘Service Distance’ between homes and open space, and X means the percentage of the people who live within this service distance. Coefficient "a" represents the distance of the residential area nearest to the water front. The coefficient "b" is a comprehensive capability index that refers to the size of the available and suitable recreational area. 5) Answers found to the questions above have implications for the planning and design of urban open space. The results from the quantitative study of recreational services of waterfront open space were applied to the assessment of river-based open space systems. It is recommended that such assessments might be done employing the network analysis function available with any GIS. In addition, several practical planning and designing suggestions are made that would help remedy any insufficient base for satisfying recreational needs. The understanding of recreational need is considered helpful for the proposing planning and designing ideas and for the changing of urban landscapes. In the course of time Tianjin's urban water system has shrunk considerably. At the same time rivers and water courses have shaped Tianjin's urban structure in noticeable ways. In the process of urbanization water has become increasingly important to the citizens and their everyday recreations. Much needs to be changed in order to improve recreational opportunities and to better provide for a livable city, most importantly when considering the increasing number of old people. Suggestions made that are based on results of this study, might be implemented in Tianjin. They are 1) to promote the quality of the waterfront open space and to make all linear waterfront area accessible recreational spaces. Then, 2), it is advisable to advocate the concept of green streets and to combine green streets with river open space in order to form an everyday recreational network. And 3) any sound urban everyday recreational service made cannot rely on only urban rivers; the whole urban structure needs to be improved, including adding small open space and optimize the form of urban communities, finally producing a multi-functional urban recreational network.

Hierarchical Object Recognition Using Libraries of Parameterized Model Sub-Parts

This thesis describes the development of a model-based vision system that exploits hierarchies of both object structure and object scale. The focus of the research is to use these hierarchies to achieve robust recognition based on effective organization and indexing schemes for model libraries. The goal of the system is to recognize parameterized instances of non-rigid model objects contained in a large knowledge base despite the presence of noise and occlusion. Robustness is achieved by developing a system that can recognize viewed objects that are scaled or mirror-image instances of the known models or that contain components sub-parts with different relative scaling, rotation, or translation than in models. The approach taken in this thesis is to develop an object shape representation that incorporates a component sub-part hierarchy- to allow for efficient and correct indexing into an automatically generated model library as well as for relative parameterization among sub-parts, and a scale hierarchy- to allow for a general to specific recognition procedure. After analysis of the issues and inherent tradeoffs in the recognition process, a system is implemented using a representation based on significant contour curvature changes and a recognition engine based on geometric constraints of feature properties. Examples of the system's performance are given, followed by an analysis of the results. In conclusion, the system's benefits and limitations are presented.

A Hierarchical Cache Coherent Protocol

As the number of processors in distributed-memory multiprocessors grows, efficiently supporting a shared-memory programming model becomes difficult. We have designed the Protocol for Hierarchical Directories (PHD) to allow shared-memory support for systems containing massive numbers of processors. PHD eliminates bandwidth problems by using a scalable network, decreases hot-spots by not relying on a single point to distribute blocks, and uses a scalable amount of space for its directories. PHD provides a shared-memory model by synthesizing a global shared memory from the local memories of processors. PHD supports sequentially consistent read, write, and test- and-set operations. This thesis also introduces a method of describing locality for hierarchical protocols and employs this method in the derivation of an abstract model of the protocol behavior. An embedded model, based on the work of Johnson[ISCA19], describes the protocol behavior when mapped to a k-ary n-cube. The thesis uses these two models to study the average height in the hierarchy that operations reach, the longest path messages travel, the number of messages that operations generate, the inter-transaction issue time, and the protocol overhead for different locality parameters, degrees of multithreading, and machine sizes. We determine that multithreading is only useful for approximately two to four threads; any additional interleaving does not decrease the overall latency. For small machines and high locality applications, this limitation is due mainly to the length of the running threads. For large machines with medium to low locality, this limitation is due mainly to the protocol overhead being too large. Our study using the embedded model shows that in situations where the run length between references to shared memory is at least an order of magnitude longer than the time to process a single state transition in the protocol, applications exhibit good performance. If separate controllers for processing protocol requests are included, the protocol scales to 32k processor machines as long as the application exhibits hierarchical locality: at least 22% of the global references must be able to be satisfied locally; at most 35% of the global references are allowed to reach the top level of the hierarchy.

Model Selection in Summary Evaluation

A difficulty in the design of automated text summarization algorithms is in the objective evaluation. Viewing summarization as a tradeoff between length and information content, we introduce a technique based on a hierarchy of classifiers to rank, through model selection, different summarization methods. This summary evaluation technique allows for broader comparison of summarization methods than the traditional techniques of summary evaluation. We present an empirical study of two simple, albeit widely used, summarization methods that shows the different usages of this automated task-based evaluation system and confirms the results obtained with human-based evaluation methods over smaller corpora.

Face Detection in Still Gray Images

We present a trainable system for detecting frontal and near-frontal views of faces in still gray images using Support Vector Machines (SVMs). We first consider the problem of detecting the whole face pattern by a single SVM classifer. In this context we compare different types of image features, present and evaluate a new method for reducing the number of features and discuss practical issues concerning the parameterization of SVMs and the selection of training data. The second part of the paper describes a component-based method for face detection consisting of a two-level hierarchy of SVM classifers. On the first level, component classifers independently detect components of a face, such as the eyes, the nose, and the mouth. On the second level, a single classifer checks if the geometrical configuration of the detected components in the image matches a geometrical model of a face.

Searching for consensus in ahp-group decision making. A bayesian perspective

This paper sets out to identify the initial positions of the different decision makers who intervene in a group decision making process with a reduced number of actors, and to establish possible consensus paths between these actors. As a methodological support, it employs one of the most widely-known multicriteria decision techniques, namely, the Analytic Hierarchy Process (AHP). Assuming that the judgements elicited by the decision makers follow the so-called multiplicative model (Crawford and Williams, 1985; Altuzarra et al., 1997; Laininen and Hämäläinen, 2003) with log-normal errors and unknown variance, a Bayesian approach is used in the estimation of the relative priorities of the alternatives being compared. These priorities, estimated by way of the median of the posterior distribution and normalised in a distributive manner (priorities add up to one), are a clear example of compositional data that will be used in the search for consensus between the actors involved in the resolution of the problem through the use of Multidimensional Scaling tools

Group preference structures in AHP–group decision making

This paper presents a procedure that allows us to determine the preference structures (PS) associated to each of the different groups of actors that can be identified in a group decision making problem with a large number of individuals. To that end, it makes use of the Analytic Hierarchy Process (AHP) (Saaty, 1980) as the technique to solve discrete multicriteria decision making problems. This technique permits the resolution of multicriteria, multienvironment and multiactor problems in which subjective aspects and uncertainty have been incorporated into the model, constructing ratio scales corresponding to the priorities relative to the elements being compared, normalised in a distributive manner (wi = 1). On the basis of the individuals’ priorities we identify different clusters for the decision makers and, for each of these, the associated preference structure using, to that end, tools analogous to those of Multidimensional Scaling. The resulting PS will be employed to extract knowledge for the subsequent negotiation processes and, should it be necessary, to determine the relative importance of the alternatives being compared using anyone of the existing procedures

Análisis estructural de la visión estratégica futura internacional de la organización para alcanzar objetivos diferenciales enfocados en contact center: MAPFRE, ANDIASISTENCIA

Por medio del estudio realizado a los diferentes enfoques y estudios hechos hacia el área de recursos humanos y cultura (organizacional y nacional) se han logrado identificar ciertos procesos y características que pueden ser implementados en el modelo de integración de operaciones de Call Center de Mapfre. Partiendo de la cultura organizacional pasando por la cultura nacional y sabiendo como ingresar y ser aceptado en una cultura internacional. Características y procesos totalmente opuestos desde su implementación pasando por sus costos y su posterior gestión; debido al choque cultural y la forma de gestión planteada por la organización basado en su modelo estructural de jerarquización y centralización de toma de decisiones. Queriendo lograr con éste trabajo generar un proyecto de unificación de un sector operativo dirigido hacia servicio al cliente y de la misma manera servir como un ejemplo a demás organizaciones nacionales o multinacionales con el objetivo de aumentar la eficiencia de su administración y la eficiencia de su estructura de costos siempre enfocado a un bien último que es el servicio al cliente.