Informatik
Refine
Year of publication
Document Type
- Preprint (748)
- Article (400)
- Working Paper (119)
- Doctoral Thesis (92)
- Diploma Thesis (46)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (35)
- diplomthesis (29)
- Report (25)
- Part of a Book (13)
- Contribution to a Periodical (10)
- Master's Thesis (6)
- Habilitation (1)
- Lecture (1)
- Review (1)
Has Fulltext
- yes (1604)
Is part of the Bibliography
- no (1604)
Keywords
Institute
- Informatik (1604)
- Frankfurt Institute for Advanced Studies (FIAS) (1002)
- Physik (982)
- Mathematik (55)
- Präsidium (41)
- Medizin (25)
- Biowissenschaften (21)
- Exzellenzcluster Makromolekulare Komplexe (8)
- Psychologie (8)
- Deutsches Institut für Internationale Pädagogische Forschung (DIPF) (5)
The effect of adding two-way communication to k cells one-way cellular automata (kC-OCAs) on their size of description is studied. kC-OCAs are a parallel model for the regular languages that consists of an array of k identical deterministic finite automata (DFAs), called cells, operating in parallel. Each cell gets information from its right neighbor only. In this paper, two models with different amounts of two-way communication are investigated. Both models always achieve quadratic savings when compared to DFAs. When compared to a one-way cellular model, the result is that minimum two-way communication can achieve at most quadratic savings whereas maximum two-way communication may provide savings bounded by a polynomial of degree k.
The descriptional complexity of iterative arrays (lAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that lAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between lAs working in linear time and lAs working in real time. Furthermore, the descriptional complexity of lAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for lAs are undecidable and not semidecidable.
It is known that deterministic finite automata (DFAs) can be algorithmically minimized, i.e., a DFA M can be converted to an equivalent DFA M' which has a minimal number of states. The minimization can be done efficiently [6]. On the other hand, it is known that unambiguous finite automata (UFAs) and nondeterministic finite automata (NFAs) can be algorithmically minimized too, but their minimization problems turn out to be NP-complete and PSPACE-complete [8]. In this paper, the time complexity of the minimization problem for two restricted types of finite automata is investigated. These automata are nearly deterministic, since they only allow a small amount of non determinism to be used. On the one hand, NFAs with a fixed finite branching are studied, i.e., the number of nondeterministic moves within every accepting computation is bounded by a fixed finite number. On the other hand, finite automata are investigated which are essentially deterministic except that there is a fixed number of different initial states which can be chosen nondeterministically. The main result is that the minimization problems for these models are computationally hard, namely NP-complete. Hence, even the slightest extension of the deterministic model towards a nondeterministic one, e.g., allowing at most one nondeterministic move in every accepting computation or allowing two initial states instead of one, results in computationally intractable minimization problems.
We study the descriptional complexity of cellular automata (CA), a parallel model of computation. We show that between one of the simplest cellular models, the realtime-OCA. and "classical" models like deterministic finite automata (DFA) or pushdown automata (PDA), there will be savings concerning the size of description not bounded by any recursive function, a so-called nonrecursive trade-off. Furthermore, nonrecursive trade-offs are shown between some restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtime-OCA. This implies that many decidability questions are not even semi decidable for cellular automata. There is no pumping lemma and no minimization algorithm for cellular automata.
Zellularautomaten sind ein massiv paralleles Berechnungsmodell, das aus sehr vielen identischen einfachen Prozessoren oder Zellen besteht, die homogen miteinander verbunden sind und parallel arbeiten. Es gibt Zellularautomaten in unterschiedlichen Ausprägungen. Beispielsweise unterscheidet man die Automaten nach der zur Verfügung stehenden Zeit, nach paralleler oder sequentieller Verarbeitung der Eingabe oder durch Beschränkungen der Kommunikation zwischen den einzelnen Zellen. Benutzt man Zellularautomaten zum Erkennen formaler Sprachen und betrachtet deren generative Mächtigkeit, dann kann bereits das einfachste zellulare Modell kontextsensitive Sprachen akzeptieren. In dieser Arbeit wird die Beschreibungskomplexität von Zellularautomaten betrachtet. Es wird untersucht, wie sich die Beschreibungsgröße einer formalen Sprache verändern kann, wenn die Sprache mit unterschiedlichen Typen von Zellularautomaten oder sequentiellen Modellen beschrieben wird. Ein wesentliches Ergebnis im ersten Teil der Arbeit ist, daß zwischen zwei Automatenklassen, deren entsprechende Sprachklassen echt ineinander enthalten oder unvergleichbar sind, nichtrekursive Tradeoffs existieren. Das heißt, der Größenzuwachs beim Wechsel von einem Automatenmodell in das andere läßt sich durch keine rekursive Funktion beschränken. Im zweiten Teil der Arbeit werden Zellularautomaten dahingehend beschränkt, daß nur eine feste Zellenzahl zugelassen ist. Zusätzlich werden Automaten mit unterschiedlichem Grad an bidirektionaler Kommunikation zwischen den einzelnen Zellen betrachtet, und es wird untersucht, welche Auswirkungen auf die Beschreibungsgröße unterschiedliche Grade an bidirektionaler Kommunikation haben können. Im Gegensatz zum unbeschränkten Modell können polynomielle und damit rekursive obere Schranken bei Umwandlungen zwischen den einzelnen Modellen bewiesen werden. Durch den Beweis unterer Schranken kann in fast allen Fällen auch die Optimalität der Konstruktionen belegt werden.
We propose a variation of online paging in two-level memory systems where pages in the fast cache get modified and therefore have to be explicitly written back to the slow memory upon evictions. For increased performance, up to alpha arbitrary pages can be moved from the cache to the slow memory within a single joint eviction, whereas fetching pages from the slow memory is still performed on a one-by-one basis. The main objective in this new alpha-paging scenario is to bound the number of evictions. After providing experimental evidence that alpha-paging can adequately model flash-memory devices in the context of translation layers we turn to the theoretical connections between alpha-paging and standard paging. We give lower bounds for deterministic and randomized alpha-paging algorithms. For deterministic algorithms, we show that an adaptation of LRU is strongly competitive, while for the randomized case we show that by adapting the classical Mark algorithm we get an algorithm with a competitive ratio larger than the lower bound by a multiplicative factor of approximately 1.7.
Die Menge digital zur Verfügung stehender Dokumente wächst zunehmend. Umso wichtiger sind adäquate Methoden, um sehr große Dokumentkollektionen durch-suchen zu können. Im Gegensatz zur exakten Suche, bei der nach Dokumenten mit bekannten Dateinamen gesucht wird, werden Techniken des Information Retrieval (IR) dazu eingesetzt, relevante Ergebnisse zu einer Anfrage ausfindig zu machen. Seit einigen Jahren werden verstärkt Kollektionen mit strukturierten Dokumenten durch¬sucht, insbesondere seit Durchsetzung der eXtensible Markup Language (XML) als offizieller Standard des World Wide Web Consortiums (W3C). Mittlerweile gibt es eine Reihe von Forschungsansätzen, bei denen IR-Methoden auf XML-Dokumente angewendet werden. XML Information Retrieval (XML-IR) nutzt dabei die Struktur der Dokumente, um die Suche nach und in denselben effektiver zu machen, d.h. die Qualität von Suchergebnissen zu verbessern, beispielsweise durch Fokussierung auf besonders relevante Dokumentteile. Die bisherigen Lösungen beziehen sich jedoch alle auf zentralisierte Stand-Alone Suchmaschinen zu Forschungszwecken. Sehr große, über eine Vielzahl von Rechnern verteilte Datenkollektionen lassen sich damit nicht durchsuchen. Techniken für verteiltes XML-IR werden in der Praxis auch dort benötigt, wo das zu durchsuchende System aus einer Vielzahl lokaler, heterogener XML-Kollektionen besteht, deren Benutzer ihre Dokumente nicht auf einem zent¬ralen Server speichern wollen oder können; solche Benutzer schließen sich häufig in Form eines dezentralen Peer-to-Peer (P2P) Netzes zusammen. Dennoch gibt es derzeit weder für Systeme im Allgemeinen, noch für P2P-Systeme im Speziellen Suchmaschinen, mit denen nach relevanten Dokumenten gesucht werden kann. In der vorliegenden Dissertation wird daher am Beispiel von P2P-Netzen erstmalig untersucht, inwiefern XML-IR in verteilten Systemen überhaupt effektiv und effizient möglich ist. Dazu wird ein allgemeines Architekturmodell für die Entwick-lung von P2P-Suchmaschinen für XML-Retrieval entworfen, in dem Funktionalität aus den Bereichen XML-IR und P2P in abstrakten Schichten angeordnet ist. Das Modell wird als Grundlage für den Entwurf einer konkreten P2P-Suchmaschine für XML-IR verwendet. Es werden dazu verschiedene Techniken für verteiltes XML-IR entwickelt, um die einzelnen Phasen der Suche umzusetzen: Indizierung der Doku¬mente, Routing der Anfragen, Ranking geeigneter Dokumente und Retrieval von Ergebnissen. Insbesondere die Problematik von aus mehreren Suchbegriffen bestehenden Multitermanfragen sowie Verteilungsaspekte werden berücksichtigt. Neben der zu erzie-lenden Suchqualität steht vor allem der notwendige Kommunikations¬aufwand im Vordergrund. Die entwickelten Methoden werden in Form einer P2P-Suchmaschine für verteiltes XML-Retrieval implementiert, die aus fast 40.000 Zeilen Java-Code besteht. Diese Suchmaschine namens SPIRIX kann voll-funktionsfähig nach XML-Dokumenten in einem P2P-Netz suchen und deren Relevanz inhaltsbasiert bewerten. Für die Kommunikation zwischen Peers wird ein P2P-Protokoll namens SpirixDHT entworfen, das auf Basis von Chord arbeitet und speziell für den Einsatz von XML-IR angepasst wird. Für die Evaluierung der entworfenen Techniken wird zunächst die Suchqualität von SPIRIX nachgewiesen. Dies geschieht durch die Teilnahme an INEX, der internationalen Initiative für die Evaluierung von XML-Retrieval. Im Rahmen von INEX werden jedes Jahr XML-IR Lösungen weltweit miteinander verglichen. Für 2008 konnte mit SPIRIX eine Suchpräzision erreicht werden, die vergleichbar mit der Qualität der Top-10 XML-IR Lösungen ist. In weiteren Experimenten werden die entworfenen Methoden für verteiltes XML-Retrieval mit INEX-Werkzeugen evaluiert; dabei werden jeweils die erzielte Such-qualität und der notwendige Aufwand gegenübergestellt. Die gewonnenen Er¬kenn-tnisse werden auf den Routingprozess angewendet; hier ist speziell die Frage-stellung interessant, wie XML-Struktur zur Performanzverbesserung in Bezug auf die Effizienz eines verteilten Systems genutzt werden kann. Die Evaluierung der konzi¬pier¬ten Routingtechniken zeigt eine signifikante Reduzierung der Anzahl versendeter Nachrichten, ihrer Größe und somit der Netzlast, wobei gleichzeitig eine Steigerung der Suchqualität erreicht wird. Im Rahmen der Dissertation wird somit der Nachweis erbracht, dass verteiltes XML-IR sowohl effektiv als auch effizient möglich ist. Zugleich wird gezeigt, wie die Ver¬wendung von XML-IR Techniken beim Routing der Anfragen dazu beitragen kann, den notwendige Suchaufwand – insbesondere den für die Kommunikation zwischen Peers – so weit zu reduzieren, dass das System auch zu einer großen Anzahl von teil¬nehmenden Peers skaliert und trotzdem eine hohe Suchqualität aufrecht erhalten werden kann.
Poster presentation: The analysis of neuronal processes distributed across multiple cortical areas aims at the identification of interactions between signals recorded at different sites. Such interactions can be described by measuring the stability of phase angles in the case of oscillatory signals or other forms of signal dependencies for less regular signals. Before, however, any form of interaction can be analyzed at a given time and frequency, it is necessary to assess whether all potentially contributing signals are present. We have developed a new statistical procedure for the detection of coincident power in multiple simultaneously recorded analog signals, allowing the classification of events as 'non-accidental co-activation'. This method can effectively operate on single trials, each lasting only for a few seconds. Signals need to be transformed into time-frequency space, e.g. by applying a short-time Fourier transformation using a Gaussian window. The discrete wavelet transform (DWT) is used in order to weight the resulting power patterns according to their frequency. Subsequently, the weighted power patterns are binarized via applying a threshold. At this final stage, significant power coincidence is determined across all subgroups of channel combinations for individual frequencies by selecting the maximum ratio between observed and expected duration of co-activation as test statistic. The null hypothesis that the activity in each channel is independent from the activity in every other channel is simulated by independent, random rotation of the respective activity patterns. We applied this procedure to single trials of multiple simultaneously sampled local field potentials (LFPs) obtained from occipital, parietal, central and precentral areas of three macaque monkeys. Since their task was to use visual cues to perform a precise arm movement, co-activation of numerous cortical sites was expected. In a data set with 17 channels analyzed, up to 13 sites expressed simultaneous power in the range between 5 and 240 Hz. On average, more than 50% of active channels participated at least once in a significant power co-activation pattern (PCP). Because the significance of such PCPs can be evaluated at the level of single trials, we are confident that this procedure is useful to study single trial variability with sufficient accuracy that much of the behavioral variability can be explained by the dynamics of the underlying distributed neuronal processes.
Poster presentation: Introduction The ability of neurons to emit different firing patterns is considered relevant for neuronal information processing. In dopaminergic neurons, prominent patterns include highly regular pacemakers with separate spikes and stereotyped intervals, processes with repetitive bursts and partial regularity, and irregular spike trains with nonstationary properties. In order to model and quantify these processes and the variability of their patterns with respect to pharmacological and cellular properties, we aim to describe the two dimensions of burstiness and regularity in a single model framework. Methods We present a stochastic spike train model in which the degree of burstiness and the regularity of the oscillation are described independently and with two simple parameters. In this model, a background oscillation with independent and normally distributed intervals gives rise to Poissonian spike packets with a Gaussian firing intensity. The variability of inter-burst intervals and the average number of spikes in each burst indicate regularity and burstiness, respectively. These parameters can be estimated by fitting the model to the autocorrelograms. This allows to assign every spike train a position in the two-dimensional space described by regularity and burstiness and thus, to investigate the dependence of the firing patterns on different experimental conditions. Finally, burst detection in single spike trains is possible within the model because the parameter estimates determine the appropriate bandwidth that should be used for burst identification. Results and Discussion We applied the model to a sample data set obtained from dopaminergic substantia nigra and ventral tegmental area neurons recorded extracellularly in vivo and studied differences between the firing activity of dopaminergic neurons in wildtype and K-ATP channel knock-out mice. The model is able to represent a variety of discharge patterns and to describe changes induced pharmacologically. It provides a simple and objective classification scheme for the observed spike trains into pacemaker, irregular and bursty processes. In addition to the simple classification, changes in the parameters can be studied quantitatively, also including the properties related to bursting behavior. Interestingly, the proposed algorithm for burst detection may be applicable also to spike trains with nonstationary firing rates if the remaining parameters are unaffected. Thus, the proposed model and its burst detection algorithm can be useful for the description and investigation of neuronal firing patterns and their variability with cellular and experimental conditions.
Poster presentation: An important challenge in neuroscience is understanding how networks of neurons go about processing information. Synapses are thought to play an essential role in cellular information processing however quantitative and mathematical models of the underlying physiologic processes that occur at synaptic active zones are lacking. We are generating mathematical models of synaptic vesicle dynamics at a well-characterized model synapse, the Drosophila larval neuromuscular junction. This synapse's simplicity, accessibility to various electrophysiological recording and imaging techniques, and the genetic malleability intrinsic to Drosophila system make it ideal for computational and mathematical studies. We have employed a reductionist approach and started by modeling single presynaptic boutons. Synaptic vesicles can be divided into different pools; however, a quantitative understanding of their dynamics at the Drosophila neuromuscular junction is lacking [4]. We performed biologically realistic simulations of high and low release probability boutons [3] using partial differential equations (PDE) taking into account not only the evolution in time but also the spatial structure in two dimensions (the extension to three dimensions will be implemented soon). PDEs are solved using UG, a program library for the calculation of multi-dimensional PDEs solved using a finite volume approach and implicit time stepping methods leading to extended linear equation systems be solvedwith multi-grid methods [3,4]. Numerical calculations are done on multi-processor computers for fast calculations using different parameters in order to asses the biological feasibility of different models. In preliminary simulations, we modeled vesicle dynamics as a diffusion process describing exocytosis as Neumann streams at synaptic active zones. The initial results obtained with these models are consistent with experimental data. However, this should be regarded as a work in progress. Further refinements will be implemented, including simulations using morphologically realistic geometries which were generated from confocal scans of the neuromuscular junction using NeuRA (a Neuron Reconstruction Algorithm). Other parameters such as glutamate diffusion and reuptake dynamics, as well as postsynaptic receptor kinetics will be incorporated as well.
Poster presentation: Introduction Dopaminergic neurons in the midbrain show a variety of firing patterns, ranging from very regular firing pacemaker cells to bursty and irregular neurons. The effects of different experimental conditions (like pharmacological treatment or genetical manipulations) on these neuronal discharge patterns may be subtle. Applying a stochastic model is a quantitative approach to reveal these changes. ...
Poster presentation: Introduction The brain is a highly interconnected network of constantly interacting units. Understanding the collective behavior of these units requires a multi-dimensional approach. The results of such analyses are hard to visualize and interpret. Hence tools capable of dealing with such tasks become imperative. ....
The pathogenesis of nodular lymphocyte–predominant Hodgkin lymphoma (NLPHL) and its relationship to other lymphomas are largely unknown. This is partly because of the technical challenge of analyzing its rare neoplastic lymphocytic and histiocytic (L&H) cells, which are dispersed in an abundant nonneoplastic cellular microenvironment. We performed a genome-wide expression study of microdissected L&H lymphoma cells in comparison to normal and other malignant B cells that indicated a relationship of L&H cells to and/or that they originate from germinal center B cells at the transition to memory B cells. L&H cells show a surprisingly high similarity to the tumor cells of T cell–rich B cell lymphoma and classical Hodgkin lymphoma, a partial loss of their B cell phenotype, and deregulation of many apoptosis regulators and putative oncogenes. Importantly, L&H cells are characterized by constitutive nuclear factor {kappa}B activity and aberrant extracellular signal-regulated kinase signaling. Thus, these findings shed new light on the nature of L&H cells, reveal several novel pathogenetic mechanisms in NLPHL, and may help in differential diagnosis and lead to novel therapeutic strategies.
Background Although current molecular clock methods offer greater flexibility in modelling historical evolutionary events, calibration of the clock with dates from the fossil record is still problematic for many groups. Here we implement several new approaches in molecular dating to estimate evolutionary ages of Lacertidae, an Old World family of lizards with a poor fossil record and uncertain phylogeny. Four different models of rate variation are tested in a new program for Bayesian phylogenetic analysis called TreeTime, based on a combination of mitochondrial and nuclear gene sequences. We incorporate paleontological uncertainty into divergence estimates by expressing multiple calibration dates as a range of probabilistic distributions. We also test the reliability of our proposed calibrations by exploring effects of individual priors on posterior estimates. Results According to the most reliable model, as indicated by Bayes factor comparison, modern lacertids arose shortly after the K/T transition and entered Africa about 45 million years ago, with the majority of their African radiation occurring in the Eocene and Oligocene. Our findings indicate much earlier origins for these clades than previously reported, and we discuss our results in light of paleogeographic trends during the Cenozoic. Conclusions This study represents the first attempt to estimate evolutionary ages of a specific group of reptiles exhibiting uncertain phylogenetic relationships, molecular rate variation and a poor fossil record. Our results emphasize the sensitivity of molecular divergence dates to fossil calibrations, and support the use of combined molecular data sets and multiple, well-spaced dates from the fossil record as minimum node constraints. The bioinformatics program used here, TreeTime, is publicly available, and we recommend its use for molecular dating of taxa faced with similar challenges.
Im heutigen Zahlungsverkehr übernehmen in zunehmendem Maße Zahlungen mit Kreditkarten eine entscheidende Rolle. Entsprechend der Verbreitung dieser Art des Zahlungsverkehrs nimmt ebenfalls der Mißbrauch mit diesem bargeldlosen Zahlungsmittel zu. Um die Verluste, die bei dem Kreditkarteninstitut auf diese Weise entstehen, so weit wie möglich einzudämmen, wird versucht, Mißbrauchstransaktionen bei der Autorisierung der Zahlungsaufforderung zu erkennen. Ziel dieser Diplomarbeit ist es zu bestimmen, in wie weit es möglich ist, illegale Transaktionen aus der Menge von Autorisierungsanfragen mit Hilfe adaptiver Algorithmen aufzudecken. Dabei sollen sowohl Methoden aus dem Bereich des Data-Mining, als auch aus den Bereichen der neuronalen Netze benutzt werden. Erschwerend bei der Mißbrauchsanalyse kommt hinzu, daß die Beurteilung der einzelnen Transaktionen in Sekundenbruchteilen abgeschlossen sein muß, um die hohe Anzahl an Autorisierungsanfragen verarbeiten zu können und den Kundenservice auf Seiten des Benutzers und des Händlers auf diese Weise zu optimieren. Weiter handelt es sich bei einem Großteil der bei der Analyse zu Verfügung stehenden Datensätze um symbolische Daten, also alpha-numerisch kodierte Werte, die stellvertretend für verschiedene Eigenschaften verwendet werden. Nur wenige der Transaktionsdaten sind analoger Natur, weisen also eine Linearität auf, die es erlaubt, "Nachbarschaften" zwischen den Daten bestimmen zu können. Damit scheidet eine reine Analyse auf Basis von neuronalen Netzwerken aus. Diese Problematik führte unter anderem zu dem verfolgten Ansatz. Als Grundlage der Analyse dienen bekannte Mißbrauchstransaktionen aus einem Zeitintervall von ungefähr einem Jahr, die jedoch aufgrund der hohen Anzahl nicht komplett als solche mit den eingehenden Transaktionen verglichen werden können, da ein sequentieller Vergleich zu viel Zeit in Anspruch nähme. Im übrigen würde durch einen einfachen Vergleich nur der schon bekannte Mißbrauch erkannt werden; eine Abstraktion der Erkenntnisse aus den Mißbrauchserfahrungen ist nicht möglich. Aus diesem Grund werden diese Mißbrauchstransaktionen mit Hilfe von Methoden aus dem Bereich des Data-Mining verallgemeinert und damit auf ein Minimum, soweit es die Verläßlichkeit dieser Datensätze zuläßt, reduziert. Desweiteren schließt sich eine Analyse der zu diesem Zeitpunkt noch nicht betrachteten analogen Daten an, um die maximale, enthaltene Information aus den Transaktionsdaten zu beziehen. Dafür werden moderne Methoden aus dem Bereich der neuronalen Netzwerke, sogenannte radiale Basisfunktionsnetze, verwendet. Da eine Mißbrauchsanalyse ohne eine entsprechende Profilanalyse unvollständig wäre, wurde abschließend mit den vorhanden Mitteln auf den zugrunde liegenden Daten in Anlehnung an die bisherige Methodik eine solche Profilauswertung und zeitabhängige Analyse realisiert. Mit dem so implementierten Modell wurde versucht, auf allgemeine Art und Weise, Verhaltens- beziehungsweise Transaktionsmuster einzuordnen und mit bei der Mißbrauchsentscheidung einfließen zu lassen. Aus den vorgestellten Analyseverfahren wurden verschiedene Klassifizierungsmodelle entwickelt, die zu guten Ergebnissen auf den Simulationsdaten führen. Es kann gezeigt werden, daß die Mißbrauchserkennung durch eine kombinierte Anwendung aus symbolischer und analoger Auswertung bestmöglich durchzuführen ist.
FIFO is the most prominent queueing strategy due to its simplicity and the fact that it only works with local information. Its analysis within the adversarial queueing theory however has shown, that there are networks that are not stable under the FIFO protocol, even at arbitrarily low rate. On the other hand there are networks that are universally stable, i.e., they are stable under every greedy protocol at any rate r < 1. The question as to which networks are stable under the FIFO protocol arises naturally. We offer the first polynomial time algorithm for deciding FIFO stability and simple-path FIFO stability of a directed network, answering an open question posed in [1, 4]. It turns out, that there are networks, that are FIFO stable but not universally stable, hence FIFO is not a worst case protocol in this sense. Our characterization of FIFO stability is constructive and disproves an open characterization in [4].
The efficient management of large multimedia databases requires the development of new techniques to process, characterize, and search for multimedia objects. Especially in the case of image data, the rapidly growing amount of documents prohibits a manual description of the images’ content. Instead, the automated characterization is highly desirable to support annotation and retrieval of digital images. However, this is a very complex and still unsolved task. To contribute to a solution of this problem, we have developed a mechanism for recognizing objects in images based on the query by example paradigm. Therefore, the most salient image features of an example image representing the searched object are extracted to obtain a scale-invariant object model. The use of this model provides an efficient and robust strategy for recognizing objects in images independently of their size. Further applications of the mechanism are classical recognition tasks such as scene decomposition or object tracking in video sequences.
For the efficient management of large image databases, the automated characterization of images and the usage of that characterization for searching and ordering tasks is highly desirable. The purpose of the project SEMACODE is to combine the still unsolved problem of content-oriented characterization of images with scale-invariant object recognition and modelbased compression methods. To achieve this goal, existing techniques as well as new concepts related to pattern matching, image encoding, and image compression are examined. The resulting methods are integrated in a common framework with the aid of a content-oriented conception. For the application, an image database at the library of the university of Frankfurt/Main (StUB; about 60000 images), the required operations are developed. The search and query interfaces are defined in close cooperation with the StUB project “Digitized Colonial Picture Library”. This report describes the fundamentals and first results of the image encoding and object recognition algorithms developed within the scope of the project.
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
Classically, encoding of images by only a few, important components is done by the Principal Component Analysis (PCA). Recently, a data analysis tool called Independent Component Analysis (ICA) for the separation of independent influences in signals has found strong interest in the neural network community. This approach has also been applied to images. Whereas the approach assumes continuous source channels mixed up to the same number of channels by a mixing matrix, we assume that images are composed by only a few image primitives. This means that for images we have less sources than pixels. Additionally, in order to reduce unimportant information, we aim only for the most important source patterns with the highest occurrence probabilities or biggest information called „Principal Independent Components (PIC)“. For the example of a synthetic picture composed by characters this idea gives us the most important ones. Nevertheless, for natural images where no a-priori probabilities can be computed this does not lead to an acceptable reproduction error. Combining the traditional principal component criteria of PCA with the independence property of ICA we obtain a better encoding. It turns out that this definition of PIC implements the classical demand of Shannon’s rate distortion theory.
We study the effect of randomness in the adversarial queueing model. All proofs of instability for deterministic queueing strategies exploit a finespun strategy of insertions by an adversary. If the local queueing decisions in the network are subject to randomness, it is far from obvious, that an adversary can still trick the network into instability. We show that uniform queueing is unstable even against an oblivious adversary. Consequently, randomizing the queueing decisions made to operate a network is not in itself a suitable fix for poor network performances due to packet pileups.
This paper describes a method to treat contextual equivalence in polymorphically typed lambda-calculi, and also how to transfer equivalences from the untyped versions of lambda-calculi to their typed variant, where our specific calculus has letrec, recursive types and is nondeterministic. An addition of a type label to every subexpression is all that is needed, together with some natural constraints for the consistency of the type labels and well-scopedness of expressions. One result is that an elementary but typed notion of program transformation is obtained and that untyped contextual equivalences also hold in the typed calculus as long as the expressions are well-typed. In order to have a nice interaction between reduction and typing, some reduction rules have to be accompanied with a type modification by generalizing or instantiating types.
Motivated by the question of correctness of a specific implementation of concurrent buffers in the lambda calculus with futures underlying Alice ML, we prove that concurrent buffers and handled futures can correctly encode each other. Correctness means that our encodings preserve and reflect the observations of may- and must-convergence. This also shows correctness wrt. program semantics, since the encodings are adequate translations wrt. contextual semantics. While these translations encode blocking into queuing and waiting, we also provide an adequate encoding of buffers in a calculus without handles, which is more low-level and uses busy-waiting instead of blocking. Furthermore we demonstrate that our correctness concept applies to the whole compilation process from high-level to low-level concurrent languages, by translating the calculus with buffers, handled futures and data constructors into a small core language without those constructs.
We show on an abstract level that contextual equivalence in non-deterministic program calculi defined by may- and must-convergence is maximal in the following sense. Using also all the test predicates generated by the Boolean, forall- and existential closure of may- and must-convergence does not change the contextual equivalence. The situation is different if may- and total must-convergence is used, where an expression totally must-converges if all reductions are finite and terminate with a value: There is an infinite sequence of test-predicates generated by the Boolean, forall- and existential closure of may- and total must-convergence, which also leads to an infinite sequence of different contextual equalities.
Driving can be dangerous. Humans become inattentive when performing a monotonous task like driving. Also the risk implied while multi-tasking, like using the cellular phone while driving, can break the concentration of the driver and increase the risk of accidents. Others factors like exhaustion, nervousness and excitement affect the performance of the driver and the response time. Consequently, car manufacturers have developed systems in the last decades which assist the driver under various circumstances. These systems are called driver assistance systems. Driver assistance systems are meant to support the task of driving, and the field of action varies from alerting the driver, with acoustical or optical warnings, to taking control of the car, such as keeping the vehicle in the traffic lane until the driver resumes control. For such a purpose, the vehicle is equipped with on-board sensors which allow the perception of the environment and/or the state of the vehicle. Cameras are sensors which extract useful information about the visual appearance of the environment. Additionally, a binocular system allows the extraction of 3D information. One of the main requirements for most camera-based driver assistance systems is the accurate knowledge of the motion of the vehicle. Some sources of information, like velocimeters and GPS, are of common use in vehicles today. Nevertheless, the resolution and accuracy usually achieved with these systems are not enough for many real-time applications. The computation of ego-motion from sequences of stereo images for the implementation of driving intelligent systems, like autonomous navigation or collision avoidance, constitutes the core of this thesis. This dissertation proposes a framework for the simultaneous computation of the 6 degrees of freedom of ego-motion (rotation and translation in 3D Euclidean space), the estimation of the scene structure and the detection and estimation of independently moving objects. The input is exclusively provided by a binocular system and the framework does not call for any data acquisition strategy, i.e. the stereo images are just processed as they are provided. Stereo allows one to establish correspondences between left and right images, estimating 3D points of the environment via triangulation. Likewise, feature tracking establishes correspondences between the images acquired at different time instances. When both are used together for a large number of points, the result is a set of clouds of 3D points with point-to-point correspondences between clouds. The apparent motion of the 3D points between consecutive frames is caused by a variety of reasons. The most dominant motion for most of the points in the clouds is caused by the ego-motion of the vehicle; as the vehicle moves and images are acquired, the relative position of the world points with respect to the vehicle changes. Motion is also caused by objects moving in the environment. They move independently of the vehicle motion, so the observed motion for these points is the sum of the ego-vehicle motion and the independent motion of the object. A third reason, and of paramount importance in vision applications, is caused by correspondence problems, i.e. the incorrect spatial or temporal assignment of the point-to-point correspondence. Furthermore, all the points in the clouds are actually noisy measurements of the real unknown 3D points of the environment. Solving ego-motion and scene structure from the clouds of points requires some previous analysis of the noise involved in the imaging process, and how it propagates as the data is processed. Therefore, this dissertation analyzes the noise properties of the 3D points obtained through stereo triangulation. This leads to the detection of a bias in the estimation of 3D position, which is corrected with a reformulation of the projection equation. Ego-motion is obtained by finding the rotation and translation between the two clouds of points. This problem is known as absolute orientation, and many solutions based on least squares have been proposed in the literature. This thesis reviews the available closed form solutions to the problem. The proposed framework is divided in three main blocks: 1) stereo and feature tracking computation, 2) ego-motion estimation and 3) estimation of 3D point position and 3D velocity. The first block solves the correspondence problem providing the clouds of points as output. No special implementation of this block is required in this thesis. The ego-motion block computes the motion of the cameras by finding the absolute orientation between the clouds of static points in the environment. Since the cloud of points might contain independently moving objects and outliers generated by false correspondences, the direct computation of the least squares might lead to an erroneous solution. The first contribution of this thesis is an effective rejection rule that detects outliers based on the distance between predicted and measured quantities, and reduces the effects of noisy measurement by assigning appropriate weights to the data. This method is called Smoothness Motion Constraint (SMC). The ego-motion of the camera between two frames is obtained finding the absolute orientation between consecutive clouds of weighted 3D points. The complete ego-motion since initialization is achieved concatenating the individual motion estimates. This leads to a super-linear propagation of the error, since noise is integrated. A second contribution of this dissertation is a predictor/corrector iterative method, which integrates the clouds of 3D points of multiple time instances for the computation of ego-motion. The presented method considerably reduces the accumulation of errors in the estimated ego-position of the camera. Another contribution of this dissertation is a method which recursively estimates the 3D world position of a point and its velocity; by fusing stereo, feature tracking and the estimated ego-motion in a Kalman Filter system. An improved estimation of point position is obtained this way, which is used in the subsequent system cycle resulting in an improved computation of ego-motion. The general contribution of this dissertation is a single framework for the real time computation of scene structure, independently moving objects and ego-motion for automotive applications.
Various concurrency primitives have been added to sequential programming languages, in order to turn them concurrent. Prominent examples are concurrent buffers for Haskell, channels in Concurrent ML, joins in JoCaml, and handled futures in Alice ML. Even though one might conjecture that all these primitives provide the same expressiveness, proving this equivalence is an open challenge in the area of program semantics. In this paper, we establish a first instance of this conjecture. We show that concurrent buffers can be encoded in the lambda calculus with futures underlying Alice ML. Our correctness proof results from a systematic method, based on observational semantics with respect to may and must convergence.
Exported proteases of Helicobacter pylori (H. pylori) are potentially involved in pathogen-associated disorders leading to gastric inflammation and neoplasia. By comprehensive sequence screening of the H. pylori proteome for predicted secreted proteases, we retrieved several candidate genes. We detected caseinolytic activities of several such proteases, which are released independently from the H. pylori type IV secretion system encoded by the cag pathogenicity island (cagPAI). Among these, we found the predicted serine protease HtrA (Hp1019), which was previously identified in the bacterial secretome of H. pylori. Importantly, we further found that the H. pylori genes hp1018 and hp1019 represent a single gene likely coding for an exported protein. Here, we directly verified proteolytic activity of HtrA in vitro and identified the HtrA protease in zymograms by mass spectrometry. Overexpressed and purified HtrA exhibited pronounced proteolytic activity, which is inactivated after mutation of Ser205 to alanine in the predicted active center of HtrA. These data demonstrate that H. pylori secretes HtrA as an active protease, which might represent a novel candidate target for therapeutic intervention strategies.
Erkennung kritischer Zustände von Patienten mit der Diagnose "Septischer Schock" mit einem RBF-Netz
(2000)
Es wurde gezeigt, dass der Arzt mit dem wachsenden RBF-Netz durch die Ausgabe von verlässlichen Warnungen unterstützt werden kann. Wie in der Clusteranalyse erläutert, leiden die Ergebnisse jedoch unter den wenigen Patienten und unter der ungenauen zeitlichen Erfassung der Daten. Da jeder Patient sehr individuelle Zustände annimmt, ist ein größeres Patientenkollektiv notwendig, um eine umfassende Wissensbasis zu lernen. Eine medizinische Nachbearbeitung der Wissensbasis durch die Analyse der Fälle ließe eine weitere Verbesserung des Ergebnisses erwarten. Somit könnten unbekannte Zusammenhänge durch das Lernen aus Beispielen und medizinisches Fachwissen kombiniert werden. Abstraktere Merkmale, die weniger abhängig von individuellen Zuständen sind, könnten eine Klassifikation noch weiter verbessern. Ein Ansatzpunkt ist z.B. die Abweichung der Messwerte vom gleitenden Mittelwert. Dieses Maß ist unempfindlicher gegenüber den individuellen Arbeitspunkten der Patienten und bildet auch die Basis von relativen Abhängigkeiten zwischen zwei Variablen, die in einem weiteren Schritt ebenfalls als Merkmal herangezogen wurden. Obwohl die Verwendung der relativen Abhängigkeiten zwischen zwei Variablen als Merkmal nicht deutlichere oder häufigere Warnungen hervorbringen konnte, weist doch die Clusteranalyse auf eine bessere Verteilung der Patienten hin. Einige Cluster sind besser für die Vorhersage geeignet, als dieses bei einer Clusterung auf Basis der Zustände erreicht werden kann. Unterstützt wird dieses Ergebnis auch durch den größeren Unterschied der Sicherheiten von falschen und richtigen Klassifikationen. Neben den bisher untersuchten Merkmalen scheinen auch die Variablen interessant zu sein, bei denen festgestellt wurde, dass sie sich trotz Medikamentengabe und adäquater Behandlung schwer stabilisieren lassen. Durch den behandelnden Arzt werden diese Werte üblicherweise in einem gewissen Bereich gehalten. Falls sich das Paar Medikament/physiologischer Parameter nicht mehr in einem sinnvollen Verhältnis befindet, kann dieses ein wichtiger Indikator sein. Nach dem Aufbau der grundlegenden Funktionalität der hier untersuchten Methoden ist die Suche nach geeigneten Merkmalen als Eingabe für ein neuronales Netz ein wesentlicher Bestandteil folgender Arbeiten. Abgesehen von dem generell anspruchsvollen Vorhaben aus Klinikdaten deutliche Hinweise für die Mortalität septischer-Schock-Patienten zu erhalten, liegen die wesentlichen Probleme in dem Umfang und der Messhäufigkeit der Frankfurter Vorstudie begründet, so dass eine Anwendung von Klassifikationsverfahren auf das umfassendere Patientenkollektiv der MEDAN Multicenter-Studie klarere Ergebnisse erwarten lässt. Eine weitere, für medizinische Anwendungen interessante, Analysemöglichkeit ist die Regelgenerierung, die zur Zeit in einem anderen Teilprojekt in der MEDAN-Arbeitsgruppe bearbeitet wird. Hier können im Fall metrischer Daten zusätzliche Hinweise für die Leistung eines reinen Klassifikationsverfahrens gewonnen werden mit dem Vorteil einer expliziten Regelausgabe. Zum anderen werden in diesem Teilprojekt auch Verfahren zur Regelgenerierung eingesetzt, die ordinale und nominale Variablen wie Diagnosen, Operationen, Therapien und Medikamentenangaben (binär, ohne genaue Dosis) auswerten können. Diese werden in den Multicenter-Daten vorhanden sein. Durch Kopplung der Regelgeneratoren für metrische Daten auf der einen Seite und für diskrete Variablen auf der anderen Seite, besteht durchaus die Hoffnung bessere Ergebnisse zu erzielen. Da der Regelgenerator für metrische Daten auf dem RBF-DDA (Abk. für: Dynamic Decay Adjustment)-Netz [BERTHOLD und DIAMOND, 1995] beruht, bietet es sich innerhalb des MEDAN-Projekts an, einen (bislang nicht durchgeführten) Vergleich mit dem hier verwendeten Netztyp durchzuführen. Der Vergleich ist allerdings nur von prinzipiellem Interesse und kann auf den hier betrachteten Daten kein grundsätzlich besseres Ergebnis liefern als die bislang durchgeführten Analysen; er kann aber zu einer umfangreichen Bewertung der Ergebnisse beitragen.
In the context of information theory, the term Mutual Information has first been formulated by Claude Elwood Shannon. Information theory is the consistent mathematical description of technical communication systems. To this day, it is the basis of numerous applications in modern communications engineering and yet became indispensable in this field. This work is concerned with the development of a concept for nonlinear feature selection from scalar, multivariate data on the basis of the mutual information. From the viewpoint of modelling, the successful construction of a realistic model depends highly on the quality of the employed data. In the ideal case, high quality data simply consists of the relevant features for deriving the model. In this context, it is important to possess a suitable method for measuring the degree of the, mostly nonlinear, dependencies between input- and output variables. By means of such a measure, the relevant features could be specifically selected. During the course of this work, it will become evident that the mutual information is a valuable and feasible measure for this task and hence the method of choice for practical applications. Basically and without the claim of being exhaustive, there are two possible constellations that recommend the application of feature selection. On the one hand, feature selection plays an important role, if the computability of a derived system model cannot be guaranteed, due to a multitude of available features. On the other hand, the existence of very few data points with a significant number of features also recommends the employment of feature selection. The latter constellation is closely related to the so called "Curse of Dimensionality". The actual statement behind this is the necessity to reduce the dimensionality to obtain an adequate coverage of the data space. In other word, it is important to reduce the dimensionality of the data, since the coverage of the data space exponentially decreases, for a constant number of data points, with the dimensionality of the available data. In the context of mapping between input- and output space, this goal is ideally reached by selecting only the relevant features from the available data set. The basic idea for this work has its origin in the rather practical field of automotive engineering. It was motivated by the goals of a complex research project in which the nonlinear, dynamic dependencies among a multitude of sensor signals should be identified. The final goal of such activities was to derive so called virtual sensors from identified dependencies among the installed automotive sensors. This enables the real-time computability of the required variable without the expenses of additional hardware. The prospect of doing without additional computing hardware is a strong motive force in particular in automotive engineering. In this context, the major problem was to find a feasible method to capture the linear- as well as the nonlinear dependencies. As mentioned before, the goal of this work is the development of a flexibly applicable system for nonlinear feature selection. The important point here is to guarantee the practicable computability of the developed method even for high dimensional data spaces, which are rather realistic in technical environments. The employed measure for the feature selection process is based on the sophisticated concept of mutual information. The property of the mutual information, regarding its high sensitivity and specificity to linear- and nonlinear statistical dependencies, makes it the method of choice for the development of a highly flexible, nonlinear feature selection framework. In addition to the mere selection of relevant features, the developed framework is also applicable for the nonlinear analysis of the temporal influences of the selected features. Hence, a subsequent dynamic modelling can be performed more efficiently, since the proposed feature selection algorithm additionally provides information about the temporal dependencies between input- and output variables. In contrast to feature extraction techniques, the developed feature selection algorithm in this work has another considerable advantage. In the case of cost intensive measurements, the variables with the highest information content can be selected in a prior feasibility study. Hence, the developed method can also be employed to avoid redundance in the acquired data and thus prevent for additional costs.
We investigate methods and tools for analysing translations between programming languages with respect to observational semantics. The behaviour of programs is observed in terms of may- and must-convergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extension.
The paper proposes a variation of simulation for checking and proving contextual equivalence in a non-deterministic call-by-need lambda-calculus with constructors, case, seq, and a letrec with cyclic dependencies. It also proposes a novel method to prove its correctness. The calculus' semantics is based on a small-step rewrite semantics and on may-convergence. The cyclic nature of letrec bindings, as well as non-determinism, makes known approaches to prove that simulation implies contextual equivalence, such as Howe's proof technique, inapplicable in this setting. The basic technique for the simulation as well as the correctness proof is called pre-evaluation, which computes a set of answers for every closed expression. If simulation succeeds in finite computation depth, then it is guaranteed to show contextual preorder of expressions.
Die Erwartungen von Studieninteressierten weichen häufig beträchtlich von den tatsächlichen Studieninhalten und Anforderungen ab. Ein Grund dafür ist, dass viele sich nicht genügend Klarheit verschaffen, welche eigenen Stärken und Schwächen für den Erfolg in Studium und Beruf »tatsächlich« relevant sind. So könnte zum Beispiel ein Abiturient mit guten Noten in Mathematik und Physik und mäßigen Zensuren in Deutsch und Englisch noch schlussfolgern, dass ihm »das Naturwissenschaftliche mehr liegt«. Ob das naturwissenschaftliche Verständnis für ein erfolgreiches Studium der Informatik jedoch gut genug ausgeprägt ist, lässt sich nicht so leicht erschließen. Noch schwieriger ist es für Studieninteressierte einzuschätzen, wie ihre »Soft Skills« ausgeprägt sind – also die Persönlichkeitsmerkmale, die in der Schule nicht systematisch beurteilt werden, jedoch hochgradig aussagekräftig für langfristigen Erfolg in Studium und Beruf sind. Ein Wechsel des Studienfaches zu Beginn des Studiums führt häufig zu einer Verlängerung der Studiendauer. Auch wenn eine derartige »Orientierungsphase« oftmals als normal und wichtig eingeschätzt wird, zeigt die praktische Erfahrung, dass Studierende mit kurzer Studiendauer jenen, die länger studiert haben, bei der Stellenvergabe tendenziell vorgezogen werden. Eine längere Studiendauer wird von Arbeitgebern häufig als Zeichen mangelnder Zielstrebigkeit oder fehlender Berufsmotivation interpretiert und kann sich so Chancen mindernd für Berufseinsteiger auswirken. Ebenso ist es im Interesse der Universitäten, die Zahl der Studienfachwechsel und -abbrüche so gering wie möglich zu halten – nicht zuletzt aus wirtschaftlichen Gründen. Deshalb bietet die Universität Frankfurt Studieninteressierten – zunächst in den Fächern Informatik und Psychologie – mit dem Self-Assessment konkrete Entscheidungshilfen an. Der verfolgte Ansatz zielt darauf ab, Abiturientinnen und Abiturienten möglichst frühzeitig und mit vertretbarem Aufwand die Möglichkeit zu bieten, selbst zu überprüfen, inwieweit ihre Erwartungen an einen Studiengang mit den tatsächlichen Inhalten und Anforderungen übereinstimmen. Das Konzept zur Erstellung eines Self-Assessments, das hier beispielhaft für den Studiengang Informatik vorgestellt wird, entstand nicht umsonst in enger Kooperation mit dem Institut für Psychologie (Prof. Dr. Helfried Moosbrugger, Dr. Siegbert Reiß, Ewa Jonkisz). Denn neben der fachlichen Qualifikation entscheiden über den Studienerfolg auch persönliche Eigenschaften wie Leistungsbereitschaft und Hartnäckigkeit. Die Auswertung des anonym durchgeführten Self-Assessments deckt außerdem Wissenslücken bei den Studieninteressierten auf, so dass eine gezielte Vorbereitung auf das Studium möglich wird. Zum Beispiel bietet der Fachbereich Mathematik und Informatik gezielte Vorbereitungskurse für Studienanfänger an, und zwar in Programmierung und Mathematik. Auch werden in den Semesterferien Repetitorien und Vorbereitungskurse angeboten – alles aus Studienbeiträgen finanziert. Auf diese Weise kann es zu einem homogeneren Kenntnisstand speziell bei den Studierenden im ersten Semester kommen. Ziel ist es, dadurch auch den »Erstsemesterschock « zu mildern. Das Online-Beratungsangebot trägt damit zu einer direkten Verbesserung der Lern- und Lehrsituation bei.
In der klassischen Theorie der formalen Sprachen gehört die Beschreibung von Sprachen durch Grammatiken oder Automaten zu den wichtigen Themen. Im Gegensatz zu diesen Modellen, die aus einer einzelnen Komponente bestehen, beschäftigt sich die Informatik heute aber immer häufiger mit verteilten Systemen, deren Komponenten auf verschiedene Art und Weise zusammenarbeiten. Eine Möglichkeit, dieses Konzept auf die Theorie der formalen Sprachen zu übertragen, ist die Definition von Grammatiksystemen. Ein Grammatiksystem besteht aus mehreren Grammatiken, die nach bestimmten Regeln zusammenarbeiten. Hauptsächlich unterscheidet man dabei zwischen sequentieller und paralleler Kooperation. In dieser Arbeitwerden kontextfreie „cooperating distributed“ (CD) Grammatiksysteme, ein Modell mit sequentieller Kooperation, betrachtet. Zur Erzeugung eines Wortes arbeiten dabei mehrere kontextfreie Grammatiken, die Komponenten, an einer gemeinsamen Satzform. Zu jedem Zeitpunkt ist immer nur eine einzige Komponente aktiv. Der Schwerpunkt der Arbeit liegt auf der Beschreibungskomplexität von CD Grammatiksystemen. Dabei wird zuerst auf die verschiedenen Maße für die Größe oder statische Komplexität eines CD Grammatiksystems eingegangen. Ein wichtiges Ergebnis im ersten Teil der Arbeit ist, daß man für CD Grammatiksysteme und insbesondere hybride CD Grammatiksysteme, eine Verallgemeinerung von kontextfreien CD Grammatiksystemen, einige dieser Maße nach oben beschränken kann. Darunter fallen die Anzahl der Komponenten und die maximale Anzahl von Produktionen in einer Komponente. Hält man einen der beiden Parameter fest, so entsteht eine unendliche Hierarchie über dem anderen Parameter. Der zweite Teil der Arbeit konzentriert sich darauf, Ergebnisse für Größenmaße zu erzielen, die nicht nur einzelne Aspekte der Komplexität, sondern die gesamte Größe oder Länge eines CD Grammatiksystems darstellen. Dafür werden CD Grammatiksysteme geeignet eingeschränkt. Man erhält metalineare Systeme und Systeme von endlichem Index. Im Gegensatz zum unbeschränkten Modell kann hier die generative Mächtigkeit sehr genau charakterisiert werden und es können Hilfsmittel wie Pumpinglemmata gezeigt werden.Weitere Resultate sind eine unendliche Hierarchie über der Breite beziehungsweise dem Index solcher Grammatiksysteme. Das wesentliches Resultat im zweiten Teil dieser Arbeit besteht daraus, daß zwischen zwei Klassen von diesen eingeschränkten CD Grammatiksystemen, deren entsprechende Sprachklassen echt ineinander enthalten sind, nichtrekursive Tradeoffs existieren. Das heißt, daß sich der Größenzuwachs beim Wechsel von der stärkeren Klasse von CD Grammatiksystemen in die schwächere durch keine rekursive Funktion beschränken läßt.
The goal of this report is to prove correctness of a considerable subset of transformations w.r.t. contextual equivalence in a an extended lambda-calculus with case, constructors, seq, let, and choice, with a simple set of reduction rules. Unfortunately, a direct proof appears to be impossible. The correctness proof is by defining another calculus comprising the complex variants of copy, case-reduction and seq-reductions that use variablebinding chains. This complex calculus has well-behaved diagrams and allows a proof that of correctness of transformations, and also that the simple calculus defines an equivalent contextual order.
Das Bumpmapping-Verfahren, eine Methode zur realistischen Darstellung rauer Oberflächen, existiert schon seit 30 Jahren, aber erst durch aktuelle Entwicklungen der Hardware lässt es sich in Echtzeitumgebungen einsetzen. Die aktuellen Verfahren ermöglichen viele darüber hinausgehende Effekte, jedoch haben sie auch mit Problemen zu kämpfen. Das Ziel dieser Diplomarbeit ist die Weiterentwicklung der Verfahren zu betrachten. In dieser Arbeit werden die Grenzen der aktuellen Bumpmapping-Algorithmen aufgezeigt und nach neuen Wegen geforscht. Das erste Verfahren erzeugt durch ein Multipassrendern fraktale Landschaften im Shader. Die darin verwendeten Methoden lassen sich für einen weiteren Algorithmus nutzen, mit dem feine Unebenheiten der Oberfläche an jedem Pixel ausgewertet werden. So können anisotrope Materialien wie gebürstete Metalle oder Mikropartikellacke simuliert werden. Den Abschluss bilden zwei neue Verfahren für prozedurale Shader. Die zu imitierende Oberfläche wird im Modell nachgebildet und per Raytracing für jeden Oberflächenpixel ausgewertet. Durch diese Methode werden viele Probleme texturbasierter Verfahren komplett umgangen.
Im Rahmen dieser Diplomarbeit wurde ein Konzept zur Extraktion von semantischen Informationen aus Wiki-Systemen entwickelt. Ausgangspunkt ist die Tatsache, dass in einem Wiki-System eine Reihe von Informationen in strukturierten, semi-strukturierten oder unstrukturierten Texten vorliegen, deren Semantik nicht immer auf den ersten Blick ersichtlich ist. Daher umfasste die Analyse zum einen, welche Informationen explizit und welche implizit vorhanden sind und zum anderen, welche Beziehungen sich aus den gefundenen Informationen ableiten lassen. Dabei handelt es sich beispielsweise um Beziehungen zwischen verschiedenen Seiten oder um Beziehungen zwischen Wörtern. Hierfür wurde eine Schablone definiert, die jede Information, die extrahiert werden kann, im Detail beschreibt. Dies beinhaltet sowohl die Semantik und die Datenquelle, aus der die Informationen extrahiert werden können, als auch eine Anleitung zur Extraktion und die abschließende Darstellung als XML-Element. Da aber nicht jede Information und deren Semantik sicher ist, wird zwischen sicheren und unsicheren Informationen unterschieden. Die Analyse hat allerdings ergeben, dass es eine Reihe an Informationen gibt, denen nicht automatisch eine Semantik zugewiesen werden kann. Außerdem wurden die Gemeinsamkeiten und Unterschiede der verschiedenen Wiki-Systeme analysiert, die für die Entwicklung des Konzeptes notwendig waren. Im Konzept ist die Gesamtarchitektur zur Extraktion von semantischen Informationen enthalten. Zwei Hauptsystemkomponenten waren hierfür notwendig: Wrapper und Mediator. Aufgrund der Unterschiede der Wiki-Systeme, wie beispielsweise die verwendete Programmiersprache, Datenbank oder Datei und Wiki-Syntax, wurde eine Wrapper eingesetzt. Der Mediator dient hingegen als Vermittler zwischen der jeweiligen Anwendung und dem Wiki-System. Durch die prototypische Implementation des Konzeptes ist die Durchführbarkeit bewiesen, bestimmte semantische Informationen zu extrahieren und diese in eine für die Weiterverarbeitung geeignete Form zu bringen. Das heißt, bestimmte Informationen können automatisch oder halb-automatisch in eine semantische Beziehung zueinander gesetzt werden.
Es ist das Ziel der vorliegenden Arbeit, die Entwicklung von Virtuellen Umgebungen und insbesondere deren Inhalte in der Art zu vereinfachen, dass die bestehende Lücke zwischen der abstrakten Beschreibung und Modellierung einer Problemstellung und der praktischen Umsetzung geschlossen wird. Dazu wurden in Kapitel 1 zunächst die Gründe und Überlegungen dargestellt, die zur Erstellung der vorliegenden Arbeit beigetragen haben. Es wurde gezeigt, dass zu einer großen Verbreitung und einer guten Integration von 3D Systemen nicht nur die Verfügbarkeit der entsprechenden Hardware gehört, sondern auch die Möglichkeit für jedermann - oder zumindest für viele - diese Techniken für die eigene Arbeit zu nutzen, wobei diese Verwendung die Erstellung von Interaktionsszenarien und Verhaltensbeschreibungen einschließt. Es wurde darauf hingewiesen, dass heutige Konzepte und Technologien der Verhaltenserstellung aufgrund ihrer Komplexität nicht zur weiten Verbreitung ausreichen, und es wurden Ideen und Vorschläge für neue Ansätze genannt. Zur Hervorhebung von Kernproblemen der heutigen Vorgehensweise bei der Erstellung Virtueller Umgebungen wurden in Kapitel 2 die Motivationen und die Überlegungen, die zu den technischen Lösungen führten, mit der Sicht und den Ansprüchen unterschiedlicher Disziplinen auf die Verhaltensbeschreibung verglichen. In diesem Zusammenhang wurden die Problematiken der Interdisziplinarität, der Verhaltenspartitionierung und der Darstellung von Verhalten vorgestellt. Das Ergebnis war die Forderung nach einem Paradigmenwechsel – weg von der technischen Orientierung, hin zu einer autorenfokussierten Erstellung Virtueller Welten. Darüber hinaus wurden grundlegende Konzepte der Ingenieurswissenschaften dargelegt. Unter Berücksichtigung der gewonnenen Erkenntnisse wurde in Kapitel 3 eine Analyse der Problemstellung anhand bestehender Arbeiten in drei Bereichen durchgeführt: Den Bereichen der manuellen und der automatisierten Erstellung sowie dem Bereich, in dem Ingenieurskonzepte auf die 3D Computergraphik angewendet werden. Aktuelle Arbeiten wurden im Hinblick darauf untersucht, welche Strukturen und Prozesse bei der Erstellung der Verhaltensbeschreibungen für Virtuelle Umgebungen auftreten und worin diese begründet sind. Zugleich wurde dabei die Unterstützung in Form von Hilfsmitteln und Vorlagen untersucht, die der Autor während der Erstellung erfährt. Es wurde aufgezeigt, dass heutige Technologien begründetermaßen meist auf einer hierarchischen Beschreibung des Inhalts aufbauen. Zum einen hilft die Hierarchie dem geübten Benutzer bei der Strukturierung und zum anderen lassen sich solche Beschreibungen schnell in ein mathematisches Modell der notwendigen Kinematik übertragen. Aber die innere Struktur einer Szene stimmt nicht notwendigerweise mit der eines baumförmigen Graphen überein. Darüber hinaus entspricht die Granularität der zum Aufbau des Szenengraphen verwendeten Elemente nicht den Vorkenntnissen der Autoren. In Kapitel 4 wurde als Lösungsansatz das Konzept der Visual Design Pattern zur Strukturbeschreibung hergeleitet. Es ermöglicht den Aufbau von Szenen aus der Perspektive des Autors. Diesem Konzept liegt die Idee zugrunde, dass in Verhaltensbeschreibungen für Virtuelle Umgebungen wiederkehrende Muster existieren, die für den Autor sichtbar und handhabbar gemacht werden sollen. Hierfür wurde basierend auf einer Betrachtung der Anforderungen und der Zielsetzung im Bereich der 3D Computergraphik, ausgehend von der ursprünglichen Idee der Design Pattern, durch eine Spezialisierung das Konzept der Visual Design Pattern zur visuellen Strukturbeschreibung Virtueller Umgebungen erarbeitet und definiert. Die Spezialisierung erfolgte im Hinblick auf die Integration einer Pattern-Visualisierung und die dadurch möglichen Interaktionsbeschreibungen zur Anpassung. Der vorgestellte Ansatz impliziert einen angepassten Produktionsprozess, bei dem die Erfahrungen und Anwendungsbeispiele, die durch ein Visual Design Pattern zusammengefasst und beschrieben sind, in der Form von Visual Templates umgesetzt wurden, so dass diese als Strukturelemente zum Aufbau neuer Szenen sowohl bei der manuellen, als auch bei der automatisierten Erstellung benutzt werden können. Die konzeptionelle Grundlage zum Aufbau der Visual Templates basiert auf dem Einsatz von 3D Komponenten als virtuelle Abbilder realer und imaginärer Entitäten. Ausgehend von den durch das Konzept der Visual Templates gegebenen Anforderungen zum einen und den Ergebnissen der Analyse zum anderen wurden die elementaren Eigenschaften für die 3D Komponenten hergeleitet und daraus die entsprechende Architektur spezifiziert. Abschließend wurde aufgezeigt, wie die erforderliche Persistenz auf der Basis eines XML-Dialekts konzeptionell umgesetzt wird. In Kapitel 5 wurde die Realisierung der vorgestellten Konzepte dargelegt. Das Konzept der Visual Design Pattern, das daraus abgeleitete Konzept der Visual Templates und das Konzept der zum Aufbau notwendigen 3D Komponenten stellen Ansätze zur Unterstützung eines Autors Virtueller Umgebungen dar. Entsprechend wurden in Kapitel 6 die beschriebenen Konzepte und deren Realisierung anhand von unterschiedlichen Anwendungsbeispielen aus den Bereichen des Notfalltrainings, der Medizin und der Innenarchitektur angewendet, wobei die Vor- und Nachteile im Vergleich zur konventionellen Erstellung analysiert wurden. Auf dieser Grundlage erfolgte zum Abschluss eine Bewertung der in dieser Arbeit vorgestellten Konzepte im Hinblick auf die erklärten Ziele. Als Kriterien dienten hierzu die vier Prinzipien der Erstellung. Demnach dient das zugrundeliegende Konzept der Visual Design Pattern in geeigneter Weise dazu, linguistische Konstruktionsmethoden zu integrieren. Durch die Nutzung der 3D-Komponenten in der Form der Component Markup Language ist es möglich geworden, diesen Ansatz auf eine formale Grundlage zu stellen und über die Visualisierung und die Anpassung in der Form von Vorlagen als visuelle Konstruktionsmethode in Autorenumgebungen zu integrieren.
Wir untersuchen das Verhalten von unären stochastischen endlichen Automaten mit Hilfe von Methoden der Theorie der homogenen Markovketten. Für unäre stochastische Automaten mit E-isoliertem Cutpoint lambda und n Zuständen bestimmen wir eine obere Schranke für die Größe des zyklischen Teils eines optimalen äquivalenten DFAs. Ein Ergebnis von Milani und Pighizzini zeigt bereits, dass für den zyklischen Teil des äquivalenten DFAs O(e exp(sqrt(n ln n))) Zustände ausreichen und in unendlich vielen Fällen auch Omega(eexp(sqrt(n ln n))) Zustände benötigt werden, wobei die Größe von E keine Rolle spielt. Wir zeigen die obere Schranke n exp (1/2E) für die Größe des zyklischen Teils und weisen nach, dass der optimale DFA für jedes c < 1 in unendlich vielen Fällen mehr als n exp (c/2E) viele Zustände im zyklischen Teil benötigt. Wir weisen auch nach, dass es eine unendliche Familie endlicher unärer Sprachen gibt, für die es jeweils einen PFA mit n Zuständen und 1/4-isoliertem Cutpoint gibt, während der optimale, DFA e exp(Omega x sqrt(n ln n)) Zustände im Anfangspfad benötigt.
Im Gegensatz zur Minimierung von DFAs ist die exakte Minimierung von NFAs oder regulären Ausdrücken nachweislich schwierig, im allgemeinen Fall PSpace-schwer. Wir zeigen, dass selbst schwache Approximationen zur Minimierung von NFAs und regulären Ausdrücken wahrscheinlich nicht effizient möglich sind. Falls als Eingabe ein NFA oder regulärer Ausdruck der Größe n gegeben ist, löst ein Approximationsalgorithmus für das Minimierungsproblem mit Approximationsfaktor o(n) bereits ein PSpace-vollständiges Problem. Wenn wir uns auf NFAs oder reguläre Ausdrücke über einem unären - also einelementigen - Alphabet beschränken, so ist das Problem der exakten Minimierung NP-vollständig. Wir weisen nach, dass effiziente Approximationen für das unäre Minimierungsproblem mit Approximationsfaktor n^(1-delta) für jedes delta>0 nicht möglich sind, sofern P != NP gilt. Liegt die Eingabe als DFA mit n Zuständen vor, kann sie exponentiell größer sein als ein äquivalenter NFA oder regulärer Ausdruck. Dennoch bleibt das Minimierungsproblem PSpace-schwer, wenn die Anzahl der Übergänge oder Zustände in einem äquivalenten NFA oder die Länge eines äquivalenten regulären Ausdrucks zu bestimmen ist. Wir zeigen, dass auch hierfür keine guten Approximationen zu erwarten sind. Unter der Annahme der Existenz von Pseudozufallsfunktionen, die wiederum auf der Annahme basiert, dass Faktorisierung schwierig ist, zeigen wir, dass kein effizienter Algorithmus einen Approximationsfaktor n/(poly(log n)) für die Zahl der Übergänge im NFA oder die Länge des regulären Ausdrucks garantieren kann. Für die Zahl der Zustände im NFA weisen wir nach, dass effiziente Approximationen mit Approximationsfaktor (n^(1/2))/(poly(log n)) ausgeschlossen sind. Wir betrachten dann Lernprobleme für reguläre Sprachen als Konzeptklasse. Mit den entwickelten Methoden, die auf der Annahme der Existenz von Pseudozufallsfunktionen beruhen, zeigen wir auch, dass es für das Problem des minimalen konsistenten DFAs keine effizienten Approximationen mit Approximationsfaktor n/(poly(log n)) gibt. Für den unären Fall hingegen weisen wir nach, dass es einen effizienten Algorithmus gibt, der einen minimalen konsistenten DFA konstruiert und erhalten somit auch einen effizienten PAC-Algorithmus für unäre reguläre Sprachen, die von DFAs mit n Zuständen akzeptiert werden. Für unäre Beispielmengen weisen wir außerdem nach, dass es keine effizienten Algorithmen gibt, die minimale konsistente NFAs konstruieren, falls NP-vollständige Probleme nicht in Zeit (n^(O(log n)) gelöst werden können. Andererseits geben wir einen effizienten Algorithmus an, der zu unären Beispielmengen einen konsistenten NFA mit höchstens O(opt^2) Zuständen konstruiert, wenn ein minimaler konsistenter NFA opt Zustände hat. Abschließend betrachten wir das Lernen von DFAs durch Äquivalenzfragen. Für den nicht-unären Fall ist bekannt, dass exponentiell viele Fragen für DFAs mit n Zuständen benötigt werden. Für unäre zyklische DFAs mit primer Zykluslänge und höchstens n Zuständen zeigen wir, dass Theta((n^2)/(ln n)) Äquivalenzfragen hinreichend und notwendig sind. Erlauben wir größere zyklische DFAs als Hypothesen, kommen wir mit weniger Fragen aus: Um zyklische DFAs mit höchstens n Zuständen durch Äquivalenzfragen mit zyklischen DFAs mit höchstens n^d Zuständen für d <= n als Hypothesen zu lernen, sind O((n^2)/d) Fragen hinreichend und Omega((n^2 ln d)/(d (ln n)^2)) Fragen nötig.
We investigate unary regular languages and compare deterministic finite automata (DFA’s), nondeterministic finite automata (NFA’s) and probabilistic finite automata (PFA’s) with respect to their size. Given a unary PFA with n states and an e-isolated cutpoint, we show that the minimal equivalent DFA has at most n exp 1/2e states in its cycle. This result is almost optimal, since for any alpha < 1 a family of PFA’s can be constructed such that every equivalent DFA has at least n exp alpha/2e states. Thus we show that for the model of probabilistic automata with a constant error bound, there is only a polynomial blowup for cyclic languages. Given a unary NFA with n states, we show that efficiently approximating the size of a minimal equivalent NFA within the factor sqrt(n)/ln n is impossible unless P = NP. This result even holds under the promise that the accepted language is cyclic. On the other hand we show that we can approximate a minimal NFA within the factor ln n, if we are given a cyclic unary n-state DFA.
Augmented Reality ist eine Technologie, mit der die Wahrnehmung der realen Umgebung durch computergenerierte Sinnesreize verändert bzw. erweitert wird. Zur Erweiterung dieser „angereicherten Realität“ werden virtuelle Informationen wie z.B. 3D-Objekte, Grafiken und Videos in Echtzeit in Abbildern der realen Umgebung dargestellt. Die Erweiterungen helfen dem Anwender Aufgaben in der Realität auszuführen, da sie ihm Informationen bereitstellen, die er – ohne AR – nicht unmittelbar wahrnehmen könnte. Die Zielsetzung ist, dem Benutzer den Eindruck zu vermitteln, dass die reale Umgebung und die virtuellen Objekte koexistent miteinander verschmelzen. Für AR-Anwendungen existieren zahlreiche potenzielle Einsatzgebiete, doch verhindern bisher einige Probleme die Verbreitung dieser Technologie. Einer breiten Nutzung von AR-Anwendungen steht beispielsweise die Problematik gegenüber, dass deren Erstellung hohe programmiertechnische Anforderungen an die Entwickler stellt. Zur Verminderung dieser Probleme ist es wünschenswert Benutzern ohne Programmierkenntnisse (Autoren) die Entwicklung von AR-Anwendungen zu ermöglichen. Zum anderen bestehen technologische Probleme bei den für die Registrierung der virtuellen Objekte essenziellen Trackingverfahren. Weiterhin weisen die bisherigen AR-Anwendungen im Allgemeinen und die mittels autorenorientierter Systeme erstellten AR-Applikationen im Besonderen Defizite bezüglich der Authentizität der Darstellungen auf. Dabei sind hauptsächlich inkorrekte Verdeckungen und unrealistische Schatten bei den virtuellen Objekten verantwortlich für den Verlust des Koexistenzeindrucks. In dieser Arbeit wird unter Berücksichtigung der Trackingprobleme und auf Basis von Analysen, die die wichtigsten Authentizitätskriterien bestimmen, ein Konzept zur authentischen Integration von virtuellen Objekten in AR-Anwendungen erarbeitet und dargelegt. Auf diesem Integrationsprozess basierend werden Konzepte für Werkzeuge mit grafischen Benutzungsschnittstellen abgeleitet, mit denen Autoren die Erstellung von AR-Anwendungen mit hoher Darstellungsauthentizität ermöglicht wird. Einerseits verfügen die mit diesen Werkzeugen erstellten AR-Anwendungen über eine verbesserte Registrierung der virtuellen Objekte. Andererseits stellen die Werkzeuge Lösungen bereit, damit die virtuellen Objekte der AR-Anwendungen korrekte Verdeckungen aufweisen und über Schatten und Schattierungseffekte verfügen, die mit der tatsächlichen Beleuchtungssituation der realen Umgebung übereinstimmen. Sämtliche dieser Autorenwerkzeuge basieren auf einem in dieser Arbeit dargelegten Prinzip, bei dem die authentische Integration mittels leicht verständlicher bzw. wenig komplexer Arbeitsschritte und auf Basis der Verwendung einer Bildsequenz der realen Zielumgebung stattfindet. Die Konzepte dieser Arbeit werden durch die Implementierung der Autorenwerkzeuge validiert. Dabei zeigt sich, dass die Konzepte technisch umsetzbar sind. Die Evaluierung basiert auf der Gegenüberstellung eines in dieser Arbeit entwickelten Anforderungskatalogs und verdeutlicht die Eignung des Integrationsprozesses und der davon abgeleiteten Konzepte der Autorenwerkzeuge. Die Autorenwerkzeuge werden in eine bestehende, frei verfügbare AR-Autorenumgebung integriert.
Raytracing und Szenengraphen
(2006)
Raytracing ist ein bekanntes Verfahren zur Erzeugung fotorealistischer Bilder. Globale Beleuchtungseffekte einer 3D-Szene werden durch das Raytracing-Verfahren physikalisch korrekt dargestellt. Erst aktuelle Forschungsarbeiten ermöglichen es, das sehr rechenintensive Verfahren bei interaktiven Bildraten in Echtzeit zu berechnen. Komplexe 3D-Szenen, wie sie beispielsweise in 3D-Spielen oder Simulationen vorkommen, können durch einen Szenengraphen modelliert und animiert werden. Damit die Rendering-Ergebnisse eines Szenengraphen näher an einem realen Bild liegen, ist es erforderlich das Raytracing-Verfahren in einen Szenengraphen einzugliedern. In dieser Arbeit werden die Möglichkeiten zur Integration eines Echtzeit-Raytracers in eine Szenengraph-API untersucht. Ziel dieser Diplomarbeit ist die Darstellung dynamischer Szenen bei interaktiven Bildraten unter Verwendung des Raytracing-Verfahrens auf einem herkömmlichen PC. Zunächst müssen bestehende Open Source Szenengraph-APIs und aktuelle Echtzeit-Raytracer auf ihre Eignung zur Integration hin überprüft werden. Bei der Verarbeitung dynamischer Szenen spielt die verwendete Beschleunigungsdatenstruktur des Raytracers eine entscheidende Rolle. Da eine komplette Neuerstellung der Datenstruktur in jedem Bild zuviel Zeit in Anspruch nimmt, ist eine schnelle und kostengünstige Aktualisierung erforderlich. Die in [LAM01] vorgestellte Lösung, eine Hüllkörperhierarchie (BVH) als Beschleunigungsdatenstruktur zu verwenden, fügt sich sehr gut in das Konzept eines Szenengraphen ein. Dadurch wird eine einfache Aktualisierung ermöglicht. Um das Ziel dieser Arbeit zu erreichen, ist es notwendig, die Parallelisierbarkeit des Raytracing-Verfahrens auszunutzen. Purcell zeigt in [Pur04], dass Grafikprozessoren (GPUs) neben ihrer eigentlichen Aufgabe auch für allgemeine, parallele Berechnungen wie das Raytracing verwendet werden können. Die in bisherigen Arbeiten über GPU-basiertes Raytracing entwickelten Systeme können dynamische Szenen nicht bei interaktiven Bildraten darstellen. Aus diesem Grund wird in dieser Diplomarbeit ein neues System konzipiert und implementiert, das den in [TS05] entwickelten Raytracer erweitert und in die Open Source Szenengraph-API OGRE 3D integriert. Das implementierte System ermöglicht die Darstellung statischer und dynamischer Szenen unter Verwendung einer Consumer-Grafikkarte bei interaktiven Bildraten. Durch seine Erweiterbarkeit bildet das System das Grundgerüst für ein Realtime-High-Quality-Rendering-System.
We model sequential synchronous circuits on the logical level by signal-processing programs in an extended lambda calculus Lpor with letrec, constructors, case and parallel or (por) employing contextual equivalence. The model describes gates as (parallel) boolean operators, memory using a delay, which in turn is modeled as a shift of the list of signals, and permits also constructive cycles due to the parallel or. It opens the possibility of a large set of program transformations that correctly transform the expressions and thus the represented circuits and provides basic tools for equivalence testing and optimizing circuits. A further application is the correct manipulation by transformations of software components combined with circuits. The main part of our work are proof methods for correct transformations of expressions in the lambda calculus Lpor, and to propose the appropriate program transformations.
This paper extends the internal frank report 28 as follows: It is shown that for a call-by-need lambda calculus LRCCP-Lambda extending the calculus LRCC-Lambda by por, i.e in a lambda-calculus with letrec, case, constructors, seq and por, copying can be done without restrictions, and also that call-by-need and call-by-name strategies are equivalent w.r.t. contextual equivalence.
Call-by-need lambda calculi with letrec provide a rewritingbased operational semantics for (lazy) call-by-name functional languages. These calculi model the sharing behavior during evaluation more closely than let-based calculi that use a fixpoint combinator. In a previous paper we showed that the copy-transformation is correct for the small calculus LR-Lambda. In this paper we demonstrate that the proof method based on a calculus on infinite trees for showing correctness of instantiation operations can be extended to the calculus LRCC-Lambda with case and constructors, and show that copying at compile-time can be done without restrictions. We also show that the call-by-need and call-by-name strategies are equivalent w.r.t. contextual equivalence. A consequence is correctness of all the transformations like instantiation, inlining, specialization and common subexpression elimination in LRCC-Lambda. We are confident that the method scales up for proving correctness of copy-related transformations in non-deterministic lambda calculi if restricted to "deterministic" subterms.
This paper proves several generic variants of context lemmas and thus contributes to improving the tools to develop observational semantics that is based on a reduction semantics for a language. The context lemmas are provided for may- as well as two variants of mustconvergence and a wide class of extended lambda calculi, which satisfy certain abstract conditions. The calculi must have a form of node sharing, e.g. plain beta reduction is not permitted. There are two variants, weakly sharing calculi, where the beta-reduction is only permitted for arguments that are variables, and strongly sharing calculi, which roughly correspond to call-by-need calculi, where beta-reduction is completely replaced by a sharing variant. The calculi must obey three abstract assumptions, which are in general easily recognizable given the syntax and the reduction rules. The generic context lemmas have as instances several context lemmas already proved in the literature for specific lambda calculi with sharing. The scope of the generic context lemmas comprises not only call-by-need calculi, but also call-by-value calculi with a form of built-in sharing. Investigations in other, new variants of extended lambda-calculi with sharing, where the language or the reduction rules and/or strategy varies, will be simplified by our result, since specific context lemmas are immediately derivable from the generic context lemma, provided our abstract conditions are met.
Fraktale Planetengenerierung
(2006)
Wie die Diplomarbeit gezeigt hat, lassen sich zwar ganze Planeten ohne größere Verzerrungen mit Hilfe fraktaler Methoden modellieren. Allerdings stößt die Darstellungsqualität an ihre Grenzen, da sich gängige Level-of-Detail-Algorithmen, wie ROAM bzw. Röttger, nicht einfach an die durch das Surface-Refinement gegebenen Bedingungen anpassen. Insbesondere die Triangulierung durch gleichseitige Dreiecke hat sich als problematisch erwiesen. Ohne diese LOD-Techniken kann aber nur eine relativ geringe Auflösung berechnet werden. Der vorgestellte Level-of-Detail-Algorithmus stellt zwar keinen Ersatz für die obengenannten Verfahren dar. Er bietet aber eine sehr gute Grundlage, denn er schränkt einfach und dadurch sehr schnell den Bereich ein, in dem sich der Betrachter bzw. die virtuelle Kamera befindet. Dies ist vorallem auch deshalb wichtig, weil die bisher entwickelten LOD-Algorithmen nur mit vergleichsweise kleinen Flächen wirklich effizient funktionieren. Eine Kombination aus dem in der Diplomarbeit entwickelten Verfahren und einem ROAM/Röttger-ähnlichen Algorithmus würde deren jeweiligen Schwächen beheben. Die eigentliche Modellierung der Landschaft bzw. der Gebirgszüge lässt sich dagegen problemlos auch auf sphärische Körper übertragen, zumindest wenn man dafür den Plasma-Algorithmus verwendet.
Reasoning about the correctness of program transformations requires a notion of program equivalence. We present an observational semantics for the concurrent lambda calculus with futures Lambda(fut), which formalizes the operational semantics of the programming language Alice ML. We show that natural program optimizations, as well as partial evaluation with respect to deterministic rules, are correct for Lambda(fut). This relies on a number of fundamental properties that we establish for our observational semantics.
Wiki-Systeme im eLearning
(2006)
Wiki-Systeme lassen sich in den verschiedensten Anwendungsgebieten auf angenehme Weise, aufgrund ihrer Open-Source Lizenz, durch die Anreicherung entsprechender Zusatzmodule anpassen. An dieser Stelle muss jedoch bedacht werden, dass durch die Integration vermehrter Funktionen, das charakteristische Merkmal der Wiki-Systeme 'Einfachheit' an Präsenz verlieren kann. Dieses, für Wikis typische Charakteristikum ist eine nicht zu unterschätzende Stärke, da sowohl die Expansion der Enzyklopädie Wikipedia, als auch die zunehmende Anzahl bestehender Wikis im Internet geradezu Beweis dafür sind, dass keine anderen Anwendungen in diesem Verhältnis existiert haben. Würde somit das Wiki, aufgrund der Anpassung an ein vorliegendes Konzept an Einfachheit verlieren, so müssten die Beweggründe des Wiki-Einsatzes noch mal überdacht werden. Ebenso könnte in den Bereichen, in denen die Stärken von Wikis unbrauchbar sind, ein anderes System womöglich bessere Ergebnisse liefern als ein Wiki. Aus diesen Gründen sollte vor einem Wiki-Einsatz überprüft werden, ob die vorhandenen Merkmale und Funktionen eines Wikis mit den eigenen Anforderungen übereinstimmen. Die im Rahmen dieser Arbeit durchgeführte Befragung hat gezeigt, das Wikis größtenteils als Präsentationsmedium, zur gemeinsamen Texterstellung und als Informationsplattform genutzt werden. Es ist deutlich geworden, dass die Integration von Wikis im Lehrbereich geeignete Anwendung findet. Auffallend war, dass zwar bei (fast) allen Befragten Schwierigkeiten aufgetreten sind und sogar erhoffte Erwartungen teilweise nicht erfüllt wurden, dennoch war der größte Teil der Befragten mit dem Wiki-Einsatz zufrieden und bewertete diesen als positiv. Die Art der aufgetretenen Schwierigkeiten und Schwachstellen zeigt, dass den Lehrenden gewisse Anleitungen und Richtlinien für einen erfolgreichen Wiki-Einsatz fehlten. Denn Informationen zum didaktischen Rahmen - in denen Wikis eingesetzt werden können - und wie Wikis eingesetzt werden sollen, waren nicht vorhanden. Somit sollen die - in dieser Arbeit - erarbeiteten Empfehlungen und Kriterien, Lehrende zu einem optimierten Wiki-Einsatz in Lehrveranstaltungen verhelfen. Außerdem sind in dieser Arbeit Vorgaben enthalten, wie Wiki-Einsätze von Lehrenden gestaltet werden können, so dass die häufig auftretenden Probleme vermieden werden können. Die erarbeiteten Empfehlungen und Kriterien sind gleichermaßen aus den positiven, wie auch aus den negativen Erfahrungen der Befragten entstanden. Insbesondere sollen die Empfehlungen und Kriterien, die von den Befragten permanent beklagten auftretenden Schwierigkeiten und Probleme verhindern. Eine Garantie jedoch, dass die Einhaltung dieser Empfehlungen und Kriterien zu einem erfolgreichen Wiki-Einsatz führen und ob keine relevanten Kriterien unbeachtet gelassen sind, kann an dieser Stelle nicht gegeben werden. Ob sich nun die Probleme, die sich mit Wiki-Einsätzen wiederholt ergeben haben, durch die Befolgung dieser Kriterien und Empfehlungen vermeiden lassen, könnte im Rahmen einer nachfolgenden Diplomarbeit untersucht werden, in der Wiki- Einsätze, begleitet werden. Weiterhin sollte im Rahmen einer weiteren Arbeit die Situation der Lernenden und die Auswirkung auf das Lernverhalten in Verbindung mit Wiki-Systemen evaluiert werden, so dass einige Thesen dieser Arbeit belegt oder gar widerlegt werden können.
ALPHA ist die Architektur einer lokationssensitiven Puppe für hydropneumatische Animation. Es ist ein Animations-Eingabegerät. Die Puppe soll ein Objekt repräsentieren, welches animiert werden soll. Ihre Gliedmaßen, welche aus Knochen und Gelenken bestehen, sind beweglich. Sie wird an einen Computer angeschlossen und die gegenwärtige Stellung ihrer Gelenke kann mittels eines ebenfalls entwickelten Treibers von diesem Computer eingelesen werden. Des Weiteren wird erklärt was eine hydropneumatische Animation ist. Die Diplomarbeit weist die folgende Gliederung auf: • Motivation • Technische Grundlagen und State-Of-The-Art-Analyse • Anforderungsanalyse • Das eigene Konzept, die lokationssensitive Puppe (ALPHA) • Evaluation • Ausblick Die Motivation beschäftigt sich mit der Entwicklung der Filmanimation und einiger Errungenschaften in der Laufbahn der Animationstechnologischen Entwicklung. Die technischen Grundlagen beschränken sich auf die Funktionsweise von Messapparaturen, welche als Gelenkstellungssensoren fungieren können. Im Einzelnen sind das der optische Resolver, der Optoencoder und die Kombination von einem Drehpotentiometer und einem Analog/Digital-Wandler. Zur State-Of-The-Art-Analyse gehört die Erläuterung bereits entwickelter Stellungs- und Bewegungsmessender Technologien, wie das Stop-Motion-Verfahren, das Motion-Capturing, das Dinosaur-Input-Device und der Datenhandschuh. Eine Zusammenstellung der Defizite dieser Verfahren schließt dieses Kapitel ab. Die Analyse der Anforderungen an ein zu entwickelndes System ist im Kapitel Anforderungsanalyse zu finden. Zum eigenen Konzept gehört die gesamte Entwicklung einer lokationssensitiven Puppe. Die Puppe ist das Ebenbild des Skeletts eines zu animierendes Objekts. Sie besteht aus mehreren Gliedmaßen, welche an ihren Gelenken beweglich sind. Die Gelenkstellung wird von Potentiometern gemessen, dessen Signal ein A/D-Wandler empfängt. Die Umschaltung der einzelnen Messwerte erfolgt über Analog-Multiplexer. Die gesamte Steuerung der Bauteile und das Auslesen des A/D-Wandler werden durch einen Treiber über den Parallelport eines PCs gesteuert. Die Funktionsweise des Treibers und seine Implementierung werden ebenfalls in diesem Kapitel erläutert. Im Kapitel Evaluation befindet sich eine Bewertung des Konzepts und der Erfüllung der Anforderungsanalyse. Schließlich zeigt der Ausblick die Möglichkeiten der Anwendungen der Puppe und einen Blick in zukünftige Technologien.