KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Thu, 08 Dec 2016 14:55:00 +0100Thu, 08 Dec 2016 14:55:00 +0100A Generic Framework for Information Segmentation in Document Images: A part-based Approach
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4508
This thesis presents a novel, generic framework for information segmentation in document images.
A document image contains different types of information, for instance, text (machine printed/handwritten), graphics, signatures, and stamps.
It is necessary to segment information in documents so that to process such segmented information only when required in automatic document processing workflows.
The main contribution of this thesis is the conceptualization and implementation of an information segmentation framework that is based on part-based features.
The generic nature of the presented framework makes it applicable to a variety of documents (technical drawings, magazines, administrative, scientific, and academic documents) digitized using different methods (scanners, RGB cameras, and hyper-spectral imaging (HSI) devices).
A highlight of the presented framework is that it does not require large training sets, rather a few training samples (for instance, four pages) lead to high performance, i.e., better than previously existing methods.
In addition, the presented framework is simple and can be adapted quickly to new problem domains.
This thesis is divided into three major parts on the basis of document digitization method (scanned, hyper-spectral imaging, and camera captured) used.
In the area of scanned document images, three specific contributions have been realized.
The first of them is in the domain of signature segmentation in administrative documents.
In some workflows, it is very important to check the document authenticity before processing the actual content.
This can be done based on the available seal of authenticity, e.g., signatures.
However, signature verification systems expect pre-segmented signature image, while signatures are usually a part of document.
To use signature verification systems on document images, it is necessary to first segment signatures in documents.
This thesis shows that the presented framework can be used to segment signatures in administrative documents.
The system based on the presented framework is tested on a publicly available dataset where it outperforms the state-of-the-art methods and successfully segmented all signatures, while less than half of the found signatures are false positives.
This shows that it can be applied for practical use.
The second contribution in the area of scanned document images is segmentation of stamps in administrative documents.
A stamp also serves as a seal for documents authenticity.
However, the location of stamp on the document can be more arbitrary than a signature depending on the person sealing the document.
This thesis shows that a system based on our generic framework is able to extract stamps of any arbitrary shape and color.
The evaluation of the presented system on a publicly available dataset shows that it is also able to segment black stamps (that were not addressed in the past) with a recall and precision of 83% and 73%, respectively.
%Furthermore, to segment colored stamps, this thesis presents a novel feature set which is based on intensity gradient, is able to extract unseen, colored, arbitrary shaped, textual as well as graphical stamps, and outperforms the state-of-the-art methods.
The third contribution in the scanned document images is in the domain of information segmentation in technical drawings (architectural floorplans, maps, circuit diagrams, etc.) containing usually a large amount of graphics and comparatively less textual components. Further, as in technical drawings, text is overlapping with graphics.
Thus, automatic analysis of technical drawings uses text/graphics segmentation as a pre-processing step.
This thesis presents a method based on our generic information segmentation framework that is able to detect the text, which is touching graphical components in architectural floorplans and maps.
Evaluation of the method on a publicly available dataset of architectural floorplans shows that it is able to extract almost all touching text components with precision and recall of 71% and 95%, respectively.
This means that almost all of the touching text components are successfully extracted.
In the area of hyper-spectral document images, two contributions have been realized.
Unlike normal three channels RGB images, hyper-spectral images usually have multiple channels that range from ultraviolet to infrared regions including the visible region.
First, this thesis presents a novel automatic method for signature segmentation from hyper-spectral document images (240 spectral bands between 400 - 900 nm).
The presented method is based on a part-based key point detection technique, which does not use any structural information, but relies only on the spectral response of the document regardless of ink color and intensity.
The presented method is capable of segmenting (overlapping and non-overlapping) signatures from varying backgrounds like, printed text, tables, stamps, logos, etc.
Importantly, the presented method can extract signature pixels and not just the bounding boxes.
This is substantial when signatures are overlapping with text and/or other objects in image. Second, this thesis presents a new dataset comprising of 300 documents scanned using a high-resolution hyper-spectral scanner. Evaluation of the presented signature segmentation method on this hyper-spectral dataset shows that it is able to extract signature pixels with the precision and recall of 100% and 79%, respectively.
Further contributions have been made in the area of camera captured document images. A major problem in the development of Optical Character Recognition (OCR) systems for camera captured document images is the lack of labeled camera captured document images datasets. In the first place, this thesis presents a novel, generic, method for automatic ground truth generation/labeling of document images. The presented method builds large-scale (i.e., millions of images) datasets of labeled camera captured / scanned documents without any human intervention. The method is generic and can be used for automatic ground truth generation of (scanned and/or camera captured) documents in any language, e.g., English, Russian, Arabic, Urdu. The evaluation of the presented method, on two different datasets in English and Russian, shows that 99.98% of the images are correctly labeled in every case.
Another important contribution in the area of camera captured document images is the compilation of a large dataset comprising 1 million word images (10 million character images), captured in a real camera-based acquisition environment, along with the word and character level ground truth. The dataset can be used for training as well as testing of character recognition systems for camera-captured documents. Various benchmark tests are performed to analyze the behavior of different open source OCR systems on camera captured document images. Evaluation results show that the existing OCRs, which already get very high accuracies on scanned documents, fail on camera captured document images.
Using the presented camera-captured dataset, a novel character recognition system is developed which is based on a variant of recurrent neural networks, i.e., Long Short Term Memory (LSTM) that outperforms all of the existing OCR engines on camera captured document images with an accuracy of more than 95%.
Finally, this thesis provides details on various tasks that have been performed in the area closely related to information segmentation. This includes automatic analysis and sketch based retrieval of architectural floor plan images, a novel scheme for online signature verification, and a part-based approach for signature verification. With these contributions, it has been shown that part-based methods can be successfully applied to document image analysis.
Sheraz Ahmeddoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4508Thu, 08 Dec 2016 14:55:00 +0100C-H Activation mediated by Transition Metal
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4503
C-H activations(C-H bond weakening effects) under impact of transition metal atoms
are theoretically investigated,
two model systems are used, one is CH3MX, the other is
n-ButMX, (X=F,Cl,Br,I,H,CN, M include all transition metal
atoms from group 4 to group 10).
Dawei Zhaodoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4503Fri, 02 Dec 2016 12:35:59 +0100A predictive-control framework to eliminate bus bunching
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4500
Buses not arriving on time and then arriving all at once - this phenomenon is known from
busy bus routes and is called bus bunching.
This thesis combines the well studied but so far separate areas of bus-bunching prediction
and dynamic holding strategies, which allow to modulate buses’ dwell times at stops to
eliminate bus bunching. We look at real data of the Dublin Bus route 46A and present
a headway-based predictive-control framework considering all components like data
acquisition, prediction and control strategies. We formulate time headways as time series
and compare several prediction methods for those. Furthermore we present an analytical
model of an artificial bus route and discuss stability properties and dynamic holding
strategies using both data available at the time and predicted headway data. In a numerical
simulation we illustrate the advantages of the presented predictive-control framework
compared to the classical approaches which only use directly available data.Matthias Andresmasterthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4500Fri, 25 Nov 2016 10:16:51 +0100Advances in Theory and Applicability of Stochastic Network Calculus
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4497
Stochastic Network Calculus (SNC) emerged from two branches in the late 90s:
the theory of effective bandwidths and its predecessor the Deterministic Network
Calculus (DNC). As such SNC’s goal is to analyze queueing networks and support
their design and control.
In contrast to queueing theory, which strives for similar goals, SNC uses in-
equalities to circumvent complex situations, such as stochastic dependencies or
non-Poisson arrivals. Leaving the objective to compute exact distributions behind,
SNC derives stochastic performance bounds. Such a bound would, for example,
guarantee a system’s maximal queue length that is violated by a known small prob-
ability only.
This work includes several contributions towards the theory of SNC. They are
sorted into four main contributions:
(1) The first chapters give a self-contained introduction to deterministic net-
work calculus and its two branches of stochastic extensions. The focus lies on the
notion of network operations. They allow to derive the performance bounds and
simplifying complex scenarios.
(2) The author created the first open-source tool to automate the steps of cal-
culating and optimizing MGF-based performance bounds. The tool automatically
calculates end-to-end performance bounds, via a symbolic approach. In a second
step, this solution is numerically optimized. A modular design allows the user to
implement their own functions, like traffic models or analysis methods.
(3) The problem of the initial modeling step is addressed with the development
of a statistical network calculus. In many applications the properties of included
elements are mostly unknown. To that end, assumptions about the underlying
processes are made and backed by measurement-based statistical methods. This
thesis presents a way to integrate possible modeling errors into the bounds of SNC.
As a byproduct a dynamic view on the system is obtained that allows SNC to adapt
to non-stationarities.
(4) Probabilistic bounds are fundamentally different from deterministic bounds:
While deterministic bounds hold for all times of the analyzed system, this is not
true for probabilistic bounds. Stochastic bounds, although still valid for every time
t, only hold for one time instance at once. Sample path bounds are only achieved by
using Boole’s inequality. This thesis presents an alternative method, by adapting
the theory of extreme values.
(5) A long standing problem of SNC is the construction of stochastic bounds
for a window flow controller. The corresponding problem for DNC had been solved
over a decade ago, but remained an open problem for SNC. This thesis presents
two methods for a successful application of SNC to the window flow controller.Michael Beckdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4497Wed, 23 Nov 2016 13:44:13 +0100Numerical Modeling for the Static and Dynamic Analysis of Nearly Incompressible Dielectric Elastomers
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4491
This thesis investigates the electromechanic coupling of dielectric elastomers for the static and dynamic case by numerical simulations. To this end, the fundamental equations of the coupled field problem are introduced and the discretisation procedure for the numerical implementation is described. Furthermore, a three field formulation is proposed and implemented to treat the nearly incompressible behaviour of the elastomer. Because of the reduced electric permittivity of the material, very high electric fields are required for actuation purposes. To improve the electromechanic coupling a heterogeneous microstructure consisting of an elastomer matrix with barium titanate inclusions is proposed and studied.Markus Klassendoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4491Fri, 11 Nov 2016 10:56:55 +0100On a structured multiscale model for acid-mediated tumor invasion: the effects of adhesion and proliferation
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4488
We propose a multiscale model for tumor cell migration in a tissue network. The system of equations involves a structured population model for the tumor cell density, which besides time and
position depends on a further variable characterizing the cellular state with respect to the amount
of receptors bound to soluble and insoluble ligands. Moreover, this equation features pH-taxis and
adhesion, along with an integral term describing proliferation conditioned by receptor binding. The
interaction of tumor cells with their surroundings calls for two more equations for the evolution of
tissue fibers and acidity (expressed via concentration of extracellular protons), respectively. The
resulting ODE-PDE system is highly nonlinear. We prove the global existence of a solution and
perform numerical simulations to illustrate its behavior, paying particular attention to the influence
of the supplementary structure and of the adhesion.Christian Engwer; Christian Stinner; Christina Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4488Fri, 11 Nov 2016 08:15:27 +0100An Adaptive and Dynamic Simulation Framework for Incremental, Collaborative Classifier Fusion
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4484
Abstract. To investigate incremental collaborative classifier fusion techniques, we have developed a comprehensive simulation framework. It is highly flexible and customizable, and can be adapted to various settings and scenarios. The toolbox is realized as an extension to the NetLogo multi-agent based simulation environment using its comprehensive Java- API. The toolbox has been integrated in two di↵erent environments, one for demonstration purposes and another, modeled on persons using re- alistic motion data from Zurich, who are communicating in an ad hoc fashion using mobile devices.Gernot Bahle; Andreas Poxrucker; George Kampis; Paul Lukowiczconferenceobjecthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4484Tue, 08 Nov 2016 13:40:49 +0100Symbolic Simulation of Mixed-Signal Systems with Extended Affine Arithmetic
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4483
Mixed-signal systems combine analog circuits with digital hardware and software systems. A particular challenge is the sensitivity of analog parts to even small deviations in parameters, or inputs. Parameters of circuits and systems such as process, voltage, and temperature are never accurate; we hence model them as uncertain values (‘uncertainties’). Uncertain parameters and inputs can modify the dynamic behavior and lead to properties of the system that are not in specified ranges. For verification of mixed- signal systems, the analysis of the impact of uncertainties on the dynamical behavior plays a central role.
Verification of mixed-signal systems is usually done by numerical simulation. A single numerical simulation run allows designers to verify single parameter values out of often ranges of uncertain values. Multi-run simulation techniques such as Monte Carlo Simulation, Corner Case simulation, and enhanced techniques such as Importance Sampling or Design-of-Experiments allow to verify ranges – at the cost of a high number of simulation runs, and with the risk of not finding potential errors. Formal and symbolic approaches are an interesting alternative. Such methods allow a comprehensive verification. However, formal methods do not scale well with heterogeneity and complexity. Also, formal methods do not support existing and established modeling languages. This fact complicates its integration in industrial design flows.
In previous work on verification of Mixed-Signal systems, Affine Arithmetic is used for symbolic simulation. This allows combining the high coverage of formal methods with the ease-of use and applicability of simulation. Affine Arithmetic computes the propagation of uncertainties through mostly linear analog circuits and DSP methods in an accurate way. However, Affine Arithmetic is currently only able to compute with contiguous regions, but does not permit the representation of and computation with discrete behavior, e.g. introduced by software. This is a serious limitation: in mixed-signal systems, uncertainties in the analog part are often compensated by embedded software; hence, verification of system properties must consider both analog circuits and embedded software.
The objective of this work is to provide an extension to Affine Arithmetic that allows symbolic computation also for digital hardware and software systems, and to demonstrate its applicability and scalability. Compared with related work and state of the art, this thesis provides the following achievements:
1. The thesis introduces extended Affine Arithmetic Forms (XAAF) for the representation of branch and merge operations.
2. The thesis describes arithmetic and relational operations on XAAF, and reduces over-approximation by using an LP solver.
3. The thesis shows and discusses ways to integrate this XAAF into existing modeling languages, in particular SystemC. This way, breaks in the design flow can be avoided.
The applicability and scalability of the approach is demonstrated by symbolic simulation of a Delta-Sigma Modulator and a PLL circuit of an IEEE 802.15.4 transceiver system.Carna Radojicicdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4483Mon, 07 Nov 2016 11:03:01 +0100Rydberg-ground state interaction in ultracold quantum gases
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4481
Combining ultracold atomic gases with the peculiar properties of Rydberg excited atoms gained a lot of theoretical and experimental attention in recent years. Embedded in the ultracold gas, an interaction between the Rydberg atom and the surrounding ground state atoms arises through the scattering of the Rydberg electron from an intruding perturber atom. This peculiar interaction gives rise to a plenitude of previously unobserved effects. Within the framework of the present thesis, this interaction is studied in detail for Rydberg \(P\)-states in rubidium.
Due to their long lifetime, atoms in Rydberg states are subject to scattering with the surrounding ground state atoms in the ultracold cloud. By measuring their lifetime as a function of the ground state atom flux, we are able to obtain the total inelastic scattering cross section as well as the partial cross section for associative ionisation. The fact that the latter is three orders of magnitude larger than the size of the formed molecular
ion indicates the presence of an efficient mass transport mechanism that is mediated by the Rydberg–ground state interaction. The immense acceleration of the collisional process shows a close analogy to a catalytic process. The increase of the scattering cross section renders associative ionisation an important process that has to be considered for experiments in dense ultracold systems.
The interaction of the Rydberg atom with a ground state perturber gives rise to a highly oscillatory potential that supports molecular bound states. These so-called ultralong-range Rydberg molecules are studied with high resolution time-of-flight spectroscopy, where we are able to determine the binding energies and lifetimes of the molecular states between the two fine structure split \(25P\)-states. Inside an electric field, we observe a broadening of the
molecular lines that indicates the presence of a permanent electric dipole moment, induced by the mixing with high angular momentum states. Due to the mixing of the ground state atom’s hyperfine states by the molecular interaction, we are able to observe a spin-flip of the perturber upon creation of a Rydberg molecule. Furthermore, an incidental near-degeneracy in the underlying level scheme of the \(25P\)-state gives rise to highly entangled states between the Rydberg fine structure state and the perturber’s hyperfine structure. These mechanisms can be used to manipulate the quantum state of a remote particle over distances that exceed by far the typical contact interaction range.
Apart from the ultralong-range Rydberg molecules that predominantly consist of only one low angular momentum state, a class of Rydberg molecules is predicted to exist that strongly mixes the high angular momentum states of the degenerate hydrogenic manifolds. These states, the so-called trilobite- and butterfly Rydberg molecules, show very peculiar properties that cannot be observed for conventional molecules. Here we present the first experimental observation of butterfly Rydberg molecules. In addition to an extensive spectroscopy that reveals the binding energy, we are also able to observe the rotational structure of these exotic molecules. The arising pendular states inside an electric field allow us, in comparison to the model of a dipolar rotor, to extract the precise bond
length and dipole moment of the molecule. With the information obtained in the present study, it is possible to photoassociate butterfly molecules with a selectable bond length, vibrational state, rotational state, and orientation inside an electric field.
By shedding light on various previously unrevealed aspects, the experiments presented in this thesis significantly deepen our knowledge on the Rydberg–ground state interaction and the peculiar effects arising from it. The obtained spectroscopic information on Rydberg molecules and the changed reaction dynamics for molecular ion creation will surely provide valuable data for quantum chemical simulations and provide necessary data to plan future experiments. Beyond that, our study reveals that the hyperfine interaction in Rydberg molecules and the peculiar properties of butterfly states provide very promising new ways to alter the short- and long-range interactions in ultracold many-body systems. In this sense the investigated Rydberg–ground state interaction not only lies right at
the interface between quantum chemistry, quantum many-body systems, and Rydberg physics, but also creates many new and fascinating possibilities by combining these fields.Thomas Niederprümdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4481Thu, 03 Nov 2016 09:25:04 +0100Verification Techniques for TSO-Relaxed Programs
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4472
Knowing the extent to which we rely on technology one may think that correct programs are nowadays the norm. Unfortunately, this is far from the truth. Luckily, possible reasons why program correctness is difficult often come hand in hand with some solutions. Consider concurrent program correctness under Sequential Consistency (SC). Under SC, instructions of each program's concurrent component are executed atomically and in order. By using logic to represent correctness specifications, model checking provides a successful solution to concurrent program verification under SC. Alas, SC’s atomicity assumptions do not reflect the reality of hardware architectures. Total Store Order (TSO) is a less common memory model implemented in SPARC and in Intel x86 multiprocessors that relaxes the SC constraints. While the architecturally de-atomized execution of stores under TSO speeds up program execution, it also complicates program verification. To be precise, due to TSO’s unbounded store buffers, a program’s semantics under TSO might be infinite. This, for example, turns reachability under SC (a PSPACE-complete task) into a non-primitive-recursive-complete problem under TSO. This thesis develops verification techniques targeting TSO-relaxed programs. To be precise, we present under- and over-approximating heuristics for checking reachability in TSO-relaxed programs as well as state-reducing methods for speeding up such heuristics. In a first contribution, we propose an algorithm to check reachability of TSO-relaxed programs lazily. The under-approximating refinement algorithm uses auxiliary variables to simulate TSO’s buffers along instruction sequences suggested by an oracle. The oracle’s deciding characteristic is that if it returns the empty sequence then the program’s SC- and TSO-reachable states are the same. Secondly, we propose several approaches to over-approximate TSO buffers. Combined in a refinement algorithm, these approaches can be used to determine safety with respect to TSO reachability for a large class of TSO-relaxed programs. On the more technical side, we prove that checking reachability is decidable when TSO buffers are approximated by multisets with tracked per address last-added-values. Finally, we analyze how the explored state space can be reduced when checking TSO and SC reachability. Intuitively, through the viewpoint of Shasha-and-Snir-like traces, we exploit the structure of program instructions to explain several state-space reducing methods including dynamic and cartesian partial order reduction.Georgel Ionut Calindoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4472Tue, 25 Oct 2016 09:15:42 +0200Modeling Road Roughness with Conditional Random Fields
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4469
A vehicles fatigue damage is a highly relevant figure in the complete vehicle design process.
Long term observations and statistical experiments help to determine the influence of differnt parts of the vehicle, the driver and the surrounding environment.
This work is focussing on modeling one of the most important influence factors of the environment: road roughness. The quality of the road is highly dependant on several surrounding factors which can be used to create mathematical models.
Such models can be used for the extrapolation of information and an estimation of the environment for statistical studies.
The target quantity we focus on in this work ist the discrete International Roughness Index or discrete IRI. The class of models we use and evaluate is a discriminative classification model called Conditional Random Field.
We develop a suitable model specification and show new variants of stochastic optimizations to train the model efficiently.
The model is also applied to simulated and real world data to show the strengths of our approach.Alexander Lemkendoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4469Mon, 17 Oct 2016 14:16:31 +0200Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4468
Multiway Quicksort, i.e., partitioning the input in one step around several pivots, has received much attention since Java 7’s runtime library uses a new dual-pivot method that outperforms by far the old Quicksort implementation. The success of dual-pivot Quicksort is most likely due to more efficient usage of the memory hierarchy, which gives reason to believe that further improvements are possible with multiway Quicksort.
In this dissertation, I conduct a mathematical average-case analysis of multiway Quicksort including the important optimization to choose pivots from a sample of the input. I propose a parametric template algorithm that covers all practically relevant partitioning methods as special cases, and analyze this method in full generality. This allows me to analytically investigate in depth what effect the parameters of the generic Quicksort have on its performance. To model the memory-hierarchy costs, I also analyze the expected number of scanned elements, a measure for the amount of data transferred from memory that is known to also approximate the number of cache misses very well. The analysis unifies previous analyses of particular Quicksort variants under particular cost measures in one generic framework.
A main result is that multiway partitioning can reduce the number of scanned elements significantly, while it does not save many key comparisons; this explains why the earlier studies of multiway Quicksort did not find it promising. A highlight of this dissertation is the extension of the analysis to inputs with equal keys. I give the first analysis of Quicksort with pivot sampling and multiway partitioning on an input model with equal keys.Sebastian Wilddoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4468Wed, 12 Oct 2016 08:20:32 +0200Signature Standard Bases over Principal Ideal Rings
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4457
By using Gröbner bases of ideals of polynomial algebras over a field, many implemented algorithms manage to give exciting examples and counter examples in Commutative Algebra and Algebraic Geometry. Part A of this thesis will focus on extending the concept of Gröbner bases and Standard bases for polynomial algebras over the ring of integers and its factors \(\mathbb{Z}_m[x]\). Moreover we implemented two algorithms for this case in Singular which use different approaches in detecting useless computations, the classical Buchberger algorithm and a F5 signature based algorithm. Part B includes two algorithms that compute the graded Hilbert depth of a graded module over a polynomial algebra \(R\) over a field, as well as the depth and the multigraded Stanley depth of a factor of monomial ideals of \(R\). The two algorithms provide faster computations and examples that lead B. Ichim and A. Zarojanu to a counter example of a question of J. Herzog. A. Duval, B. Goeckner, C. Klivans and J. Martin have recently discovered a counter example for the Stanley Conjecture. We prove in this thesis that the Stanley Conjecture holds in some special cases. Part D explores the General Neron Desingularization in the frame of Noetherian local domains of dimension 1. We have constructed and implemented in Singular and algorithm that computes a strong Artin Approximation for Cohen-Macaulay local rings of dimension 1. Adrian Popescudoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4457Tue, 04 Oct 2016 09:49:56 +0200Integrating Security Concerns into Safety Analysis of Embedded Systems Using Component Fault Trees
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4455
Nowadays, almost every newly developed system contains embedded systems for controlling system functions. An embedded system perceives its environment via sensors, and interacts with it using actuators such as motors. For systems that might damage their environment by faulty behavior usually a safety analysis is performed. Security properties of embedded systems are usually not analyzed at all. New developments in the area of Industry 4.0 and Internet of Things lead to more and more networking of embedded systems. Thereby, new causes for system failures emerge: Vulnerabilities in software and communication components might be exploited by attackers to obtain control over a system. By targeted actions a system may also be brought into a critical state in which it might harm itself or its environment. Examples for such vulnerabilities, and also successful attacks, became known over the last few years.
For this reason, in embedded systems safety as well as security has to be analyzed at least as far as it may cause safety critical failures of system components.
The goal of this thesis is to describe in one model how vulnerabilities from the security point of view might influence the safety of a system. The focus lies on safety analysis of systems, so the safety analysis is extended to encompass security problems that may have an effect on the safety of a system. Component Fault Trees are very well suited to examine causes of a failure and to find failure scenarios composed of combinations of faults. A Component Fault Tree of an analyzed system is extended by additional Basic Events that may be caused by targeted attacks. Qualitative and quantitative analyses are extended to take the additional security events into account. Thereby, causes of failures that are based on safety as well as security problems may be found. Quantitative or at least semi-quantitative analyses allow to evaluate security measures more detailed, and to justify the need of such.
The approach was applied to several example systems: The safety chain of the off-road robot RAVON, an adaptive cruise control, a smart farming scenario, and a model of a generic infusion pump were analyzed. The result of all example analyses was that additional failure causes were found which would not have been detected in traditional Component Fault Trees. In the analyses also failure scenarios were found that are caused solely by attacks, and that are not depending on failures of system components. These are especially critical scenarios which should not happen in this way, as they are not found in a classical safety analysis. Thus the approach shows its additional benefit to a safety analysis which is achieved by the application of established techniques with only little additional effort.Max Steinerdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4455Tue, 27 Sep 2016 12:49:38 +0200On a coupled SDE-PDE system modeling acid-mediated tumor invasion
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4451
We propose and analyze a multiscale model for acid-mediated tumor invasion
accounting for stochastic effects on the subcellular level.
The setting involves a PDE of reaction-diffusion-taxis type describing the evolution of the tumor cell density,
the movement being directed towards pH gradients in the local microenvironment,
which is coupled to a PDE-SDE system characterizing the
dynamics of extracellular and intracellular proton concentrations, respectively.
The global well-posedness of the model is shown and
numerical simulations are performed in order to illustrate the solution behavior.Sandesh Athni Hiremath; Anna Zhigun; Stefanie Sonner; Christina Surulescupreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4451Thu, 22 Sep 2016 08:23:05 +0200Treatment of Reissner–Mindlin shells with kinks without the need for drilling rotation stabilization in an isogeometric framework
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4448
This work presents a framework for the computation of complex geometries containing intersections of multiple patches with Reissner-Mindlin shell elements. The main objective is to provide an isogeometric finite element implementation which neither requires drilling rotation stabilization, nor user interaction to quantify the number of rotational degrees of freedom for every node. For this purpose, the following set of methods is presented. Control points with corresponding physical location are assigned to one common node for the finite element solution. A nodal basis system in every control point is defined, which ensures an exact interpolation of the director vector throughout the whole domain. A distinction criterion for the automatic quantification of rotational degrees of freedom for every node is presented. An isogeometric Reissner-Mindlin shell formulation is enhanced to handle geometries with kinks and allowing for arbitrary intersections of patches. The parametrization of adjacent patches along the interface has to be conforming. The shell formulation is derived from the continuum theory and uses a rotational update scheme for the current director vector. The nonlinear kinematic allows the computation of large deformations and large rotations. Two concepts for the description of rotations are presented. The first one uses an interpolation which is commonly used in standard Lagrange-based shell element formulations. The second scheme uses a more elaborate concept proposed by the authors in prior work, which increases the accuracy for arbitrary curved geometries. Numerical examples show the high accuracy and robustness of both concepts. The applicability of the proposed framework is demonstrated.
Wolfgang Dornisch; Sven Klinkelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4448Fri, 16 Sep 2016 12:50:46 +0200Isogeometric Reissner–Mindlin shell analysis with exactly calculated director vectors
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4447
An isogeometric Reissner-Mindlin shell derived from the continuum theory is presented. The geometry is described by NURBS surfaces. The kinematic description of the employed shell theory requires the interpolation of the director vector and of a local basis system. Hence, the definition of nodal basis systems at the control points is necessary for the proposed formulation. The control points are in general not located on the shell reference surface and thus, several choices for the nodal values are possible. The proposed new method uses the higher continuity of the geometrical description to calculate nodal basis system and director vectors which lead to geometrical exact interpolated values thereof. Thus, the initial director vector coincides with the normal vector even for the coarsest mesh. In addition to that a more accurate interpolation of the current director and its variation is proposed. Instead of the interpolation of nodal director vectors the new approach interpolates nodal rotations. Account is taken for the discrepancy between interpolated basis systems and the individual nodal basis systems with an additional transformation. The exact evaluation of the initial director vector along with the interpolation of the nodal rotations lead to a shell formulation which yields precise results even for coarse meshes. The convergence behavior is shown to be correct for k-refinement allowing the use of coarse meshes with high orders of NURBS basis functions. This is potentially advantageous for applications with high numerical effort per integration point. The geometrically nonlinear formulation accounts for large rotations. The consistent tangent matrix is derived. Various standard benchmark examples show the superior accuracy of the presented shell formulation. A new benchmark designed to test the convergence behavior for free form surfaces is presented. Despite the higher numerical effort per integration point the improved accuracy yields considerable savings in computation cost for a predefined error bound.
Wolfgang Dornisch; Sven Klinkel; Bernd Simeonpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4447Mon, 12 Sep 2016 10:12:58 +0200The weak substitution method – An application of the mortar method for patch coupling in NURBS-based isogeometric analysis
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4436
In this contribution a mortar-type method for the coupling of non-conforming NURBS surface patches is proposed. The connection of non-conforming patches with shared degrees of freedom requires mutual refinement, which propagates throughout the whole patch due to the tensor-product structure of NURBS surfaces. Thus, methods to handle non-conforming meshes are essential in NURBS-based isogeometric analysis. The main objective of this work is to provide a simple and efficient way to couple the individual patches of complex geometrical models without altering the variational formulation. The deformations of the interface control points of adjacent patches are interrelated with a master-slave relation. This relation is established numerically using the weak form of the equality of mutual deformations along the interface. With the help of this relation the interface degrees of freedom of the slave patch can be condensated out of the system. A natural connection of the patches is attained without additional terms in the weak form. The proposed method is also applicable for nonlinear computations without further measures. Linear and geometrical nonlinear examples show the high accuracy and robustness of the new method. A comparison to reference results and to computations with the Lagrange multiplier method is given.Wolfgang Dornisch; Gennaro Vitucci; Sven Klinkelpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4436Fri, 09 Sep 2016 08:57:48 +0200The Xilinx Zynq: A Modern System on Chip for Software Defined Radios
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4442
Software defined radios can be implemented on general purpose processors (CPUs), e.g. based on a PC. A processor offers high flexibility: It can not only be used to process the data samples, but also to control receiver functions, display a waterfall or run demodulation software. However, processors can only handle signals of limited bandwidth due to their comparatively low processing speed. For signals of high bandwidth the SDR algorithms have to be implemented as custom designed digital circuits on an FPGA chip. An FPGA provides a very high processing speed, but also lacks flexibility and user interfaces. Recently the FPGA manufacturer Xilinx has
introduced a hybrid system on chip called Zynq, that combines both approaches. It features a dual ARM Cortex-A9 processor and an FPGA, that offer the flexibility of a processor with the processing speed of an FPGA on a single chip. The Zynq is therefore very interesting for use in SDRs. In this paper the
application of the Zynq and its evaluation board (Zedboard) will be discussed. As an example, a direct sampling receiver has been implemented on the Zedboard using a high-speed 16 bit ADC with 250 Msps.Stefan Schollarticlehttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4442Wed, 07 Sep 2016 14:45:32 +0200A Phase Field Model for the Evolution of Martensite Microstructures in Metastable Austenites
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4438
This thesis is concerned with a phase field model for martensitic transformations in metastable austenitic steels. Within the phase field approach an order parameter is introduced to indicate whether the present phase is austenite or martensite. The evolving microstructure is described by the evolution of the order parameter, which is assumed to follow the time-dependent Ginzburg-Landau equation. The elastic phase field model is enhanced in two different ways to take further phenomena into account. First, dislocation movement is considered by a crystal plasticity setting. Second, the elastic model for martensitic transformations is combined with a phase field model for fracture. Finite element simulations are used to study the single effects separately which contribute to the microstructure formation.Regina Müllerdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4438Tue, 06 Sep 2016 17:37:25 +0200Cyanobacterial lichenized fungi and there photobionts in Vietnam
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4437
The biodiversity of the cyanobacterial lichen flora of Vietnam is chronically understudied. Previous studies often neglected the lichens that inhabit lowlands especially outcrops and sand dunes that are common habitats in Vietnam.
A cyanolichen collection was gathered from lowlands of central and southern Vietnam to study their diversity and distribution. At the same time, cultured photobionts from those lichens were used for olyphasic taxonomic approach.
A total of 66 cyanolichens were recorded from lowland regions in central and southern of Vietnam, doubles the number of cyanolichens for Vietnam. 80% of them are new records for Vietnam in which a new species Pyrenopsis melanophthalma and two new unidentified lichinacean taxa were described.
A notably floristic segregation by habitats was indicated in the communities. Saxicolous Lichinales dominated in coastal outcrops that corresponded to 56% of lichen species richness. Lecanoralean cyanolichens and basidiolichens were found in the lowland forests. Precipitation correlated negatively to species richness in this study, indicating a competitive relationship.
Eleven cyanobacterial strains including 8 baeocyte-forming members of the genus Chroococcidiopsis and 3 heterocyte-forming species of the genera Nostoc and Scytonema were successfully isolated from lichens.
Phylogenetic and morphological analyses indicated that Chroococcidiopsis was the unique photobiont in Peltula. New mophological characters were found in two Chroococcidiopsis strains: (1) the purple content of cells in one photobiont strain that was isolated from a new lichinacean taxon, and (2) the pseudofilamentous feature by binary division from a strain that was isolated from Porocyphus dimorphus.
With respect to heterocyte-forming cyanobiont, Scytonema was confirmed as the photobiont in the ascolichen Heppia lutosa applying the polyphasic method. The genus Scytonema in the basidiolichens Cyphellostereum was morphologically examinated in lichen thalli. For the first time the intracellular haustorial system of basidiolichen genus Cyphellostereum was noted and investigated.
Phylogenetic analysis of photobiont strains Nostoc from Pannaria tavaresii and Parmeliella brisbanensis indicated that a high selectivity occurred in Parmeliella brisbanensis that were from different regions of the world, while low photobiont selectivity occurred among Pannaria tavaresii samples from different geographical regions.
The herewith presented dissertation is therefore an important contribution to the lichen flora of Vietnam and a significant improvement of the actual knowledge about cyanolichens in this country.Giao Thi Phi Vodoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4437Mon, 05 Sep 2016 16:34:37 +0200Morphology and Morphology Formation of Injection Molded PP-based Nanocomposites
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4433
The mechanical properties of semi-crystalline polymers depend extremely on their
morphology, which is dependent on the crystallization during processing. The aim of
this research is to determine the effect of various nanoparticles on morphology
formation and tensile mechanical properties of polypropylene under conditions
relevant in polymer processing and to contribute ultimately to the understanding of
this influence.
Based on the thermal analyses of samples during fast cooling, it is found that the
presence of nanoparticle enhances the overall crystallization process of PP. The results
suggest that an increase of the nucleation density/rate is a dominant process that
controls the crystallization process of PP in this work, which can help to reduce the
cycle time in the injection process. Moreover, the analysis of melting behaviors
obtained after each undercooling reveals that crystal perfection increases significantly
with the incorporation of TiO2 nanoparticles, while it is not influenced by the SiO2
nanoparticles.
This work also comprises an analysis of the influence of nanoparticles on the
microstructure of injection-molded parts. The results clearly show multi-layers along
the wall thickness. The spherulite size and the degree of crystallinity continuously
decrease from the center to the edge. Generally both the spherulite size and the degree
of crystallinity decrease with higher the SiO2 loading. In contrast, an increase in the
degree of crystallinity with an increasing TiO2 nanoparticle loading was detected.
The tensile properties exhibit a tendency to increase in the tensile strength as the core
is reached. The tensile strength decreases with the addition of nanoparticles, while the
elongation at break of nanoparticle-filled PP decreases from the skin to the core. With
increasing TiO2 loading, the elongation at break decreases.Buncha Suksutdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4433Thu, 25 Aug 2016 09:19:31 +0200Worst-Case Performance Analysis of Feed-Forward Networks – An Efficient and Accurate Network Calculus
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4432
Distributed systems are omnipresent nowadays and networking them is fundamental for the continuous dissemination and thus availability of data. Provision of data in real-time is one of the most important non-functional aspects that safety-critical networks must guarantee. Formal verification of data communication against worst-case deadline requirements is key to certification of emerging x-by-wire systems. Verification allows aircraft to take off, cars to steer by wire, and safety-critical industrial facilities to operate. Therefore, different methodologies for worst-case modeling and analysis of real-time systems have been established. Among them is deterministic Network Calculus (NC), a versatile technique that is applicable across multiple domains such as packet switching, task scheduling, system on chip, software-defined networking, data center networking and network virtualization. NC is a methodology to derive deterministic bounds on two crucial performance metrics of communication systems:
(a) the end-to-end delay data flows experience and
(b) the buffer space required by a server to queue all incoming data.
NC has already seen application in the industry, for instance, basic results have been used to certify the backbone network of the Airbus A380 aircraft.
The NC methodology for worst-case performance analysis of distributed real-time systems consists of two branches. Both share the NC network model but diverge regarding their respective derivation of performance bounds, i.e., their analysis principle. NC was created as a deterministic system theory for queueing analysis and its operations were later cast in a (min,+)-algebraic framework. This branch is known as algebraic Network Calculus (algNC). While algNC can efficiently compute bounds on delay and backlog, the algebraic manipulations do not allow NC to attain the most accurate bounds achievable for the given network model. These tight performance bounds can only be attained with the other, newly established branch of NC, the optimization-based analysis (optNC). However, the only optNC analysis that can currently derive tight bounds was proven to be computationally infeasible even for the analysis of moderately sized networks other than simple sequences of servers.
This thesis makes various contributions in the area of algNC: accuracy within the existing framework is improved, distributivity of the sensor network calculus analysis is established, and most significantly the algNC is extended with optimization principles. They allow algNC to derive performance bounds that are competitive with optNC. Moreover, the computational efficiency of the new NC approach is improved such that this thesis presents the first NC analysis that is both accurate and computationally feasible at the same time. It allows NC to scale to larger, more complex systems that require formal verification of their real-time capabilities.Steffen Bondorfdoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4432Mon, 22 Aug 2016 13:59:02 +0200Gröbner Bases over Extention Fields of \(\mathbb{Q}\)
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4428
Gröbner bases are one of the most powerful tools in computer algebra and commutative algebra, with applications in algebraic geometry and singularity theory. From the theoretical point of view, these bases can be computed over any field using Buchberger's algorithm. In practice, however, the computational efficiency depends on the arithmetic of the coefficient field.
In this thesis, we consider Gröbner bases computations over two types of coefficient fields. First, consider a simple extension \(K=\mathbb{Q}(\alpha)\) of \(\mathbb{Q}\), where \(\alpha\) is an algebraic number, and let \(f\in \mathbb{Q}[t]\) be the minimal polynomial of \(\alpha\). Second, let \(K'\) be the algebraic function field over \(\mathbb{Q}\) with transcendental parameters \(t_1,\ldots,t_m\), that is, \(K' = \mathbb{Q}(t_1,\ldots,t_m)\). In particular, we present efficient algorithms for computing Gröbner bases over \(K\) and \(K'\). Moreover, we present an efficient method for computing syzygy modules over \(K\).
To compute Gröbner bases over \(K\), starting from the ideas of Noro [35], we proceed by joining \(f\) to the ideal to be considered, adding \(t\) as an extra variable. But instead of avoiding superfluous S-pair reductions by inverting algebraic numbers, we achieve the same goal by applying modular methods as in [2,4,27], that is, by inferring information in characteristic zero from information in characteristic \(p > 0\). For suitable primes \(p\), the minimal polynomial \(f\) is reducible over \(\mathbb{F}_p\). This allows us to apply modular methods once again, on a second level, with respect to the
modular factors of \(f\). The algorithm thus resembles a divide and conquer strategy and
is in particular easily parallelizable. Moreover, using a similar approach, we present an algorithm for computing syzygy modules over \(K\).
On the other hand, to compute Gröbner bases over \(K'\), our new algorithm first specializes the parameters \(t_1,\ldots,t_m\) to reduce the problem from \(K'[x_1,\ldots,x_n]\) to \(\mathbb{Q}[x_1,\ldots,x_n]\). The algorithm then computes a set of Gröbner bases of specialized ideals. From this set of Gröbner bases with coefficients in \(\mathbb{Q}\), it obtains a Gröbner basis of the input ideal using sparse multivariate rational interpolation.
At current state, these algorithms are probabilistic in the sense that, as for other modular Gröbner basis computations, an effective final verification test is only known for homogeneous ideals or for local monomial orderings. The presented timings show that for most examples, our algorithms, which have been implemented in SINGULAR [17], are considerably faster than other known methods.Dereje Kifle Bokudoctoralthesishttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4428Wed, 10 Aug 2016 15:34:30 +0200Regionalized Assortment Planning for Multiple Chain Stores: Complexity, Approximability, and Solution Methods
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4424
In retail, assortment planning refers to selecting a subset of products to offer that maximizes profit. Assortments can be planned for a single store or a retailer with multiple chain stores where demand varies between stores. In this paper, we assume that a retailer with a multitude of stores wants to specify her offered assortment. To suit all local preferences, regionalization and store-level assortment optimization are widely used in practice and lead to competitive advantages. When selecting regionalized assortments, a tradeoff between expensive, customized assortments in every store and inexpensive, identical assortments in all stores that neglect demand variation is preferable.
We formulate a stylized model for the regionalized assortment planning problem (APP) with capacity constraints and given demand. In our approach, a 'common assortment' that is supplemented by regionalized products is selected. While products in the common assortment are offered in all stores, products in the local assortments are customized and vary from store to store.
Concerning the computational complexity, we show that the APP is strongly NP-complete. The core of this hardness result lies in the selection of the common assortment. We formulate the APP as an integer program and provide algorithms and methods for obtaining approximate solutions and solving large-scale instances.
Lastly, we perform computational experiments to analyze the benefits of regionalized assortment planning depending on the variation in customer demands between stores.Michael Hopf; Clemens Thielen; Benedikt Kasper; Hans Corstenworkingpaperhttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4424Tue, 09 Aug 2016 09:43:13 +0200