Informatik
Refine
Year of publication
- 2004 (24) (remove)
Document Type
- diplomthesis (6)
- Article (5)
- Diploma Thesis (4)
- Conference Proceeding (3)
- Working Paper (3)
- Report (2)
- Doctoral Thesis (1)
Has Fulltext
- yes (24)
Is part of the Bibliography
- no (24)
Keywords
- Textanalyse ; Linguistische Datenverarbeitung; Computerlinguistik (3)
- septic shock (2)
- Beschreibungskomplexität (1)
- Caché (1)
- Householder reflection (1)
- InterSystems (1)
- Interpretierer (1)
- LLL-reduction (1)
- Operationale Semantik (1)
- RDF (1)
Institute
- Informatik (24)
- Mathematik (2)
- Biowissenschaften (1)
- Geowissenschaften (1)
- Senckenbergische Naturforschende Gesellschaft (1)
In dieser Diplomarbeit wurde zunächst eine Einführung in das Gebiet der Unifikationstheorie gegeben, um dann zum Teilgebiet des Kontextmatchings zu kommen. Dieses wurde in das Gesamtgebiet der Unifikation eingeordnet. In Anlehnung an [Schm2003] wurde die Komplexität einiger Einschränkungen des Kontextmatchings betrachtet. Insbesondere wurde ein Algorithmus zur Lösung linearer Kontextmatchingprobleme in polynomieller Zeit vorgestellt. Es folgte die Einführung des Transformationsalgorithmus aus [Schm2003] zur Lösung allgemeiner Kontextmatchingprobleme, wobei nach und nach verbesserte Transformationsregeln für einzelne spezielle Problemsituationen vorgestellt wurden. Über [Schm2003] hinausgehend wurden die Regeln Split: Korrespondierende Lochpfade und Konstantenelimination vorgestellt. Im Rahmen der Diplomarbeit wurden die genannten Algorithmen in der funktionalen Programmiersprache Haskell implementiert, wobei auf eine einfache Erweiterbarkeit um neue Transformationsregeln sowie alternative Heuristiken zur Auswahl der in einem Schritt anzuwendenden Transformationsregel geachtet wurde. Die Implementierung (und damit auch die in ihr implementierten Algorithmen) wurde mit Hilfe von zufällig erzeugten Termen auf ihre Leistungsfähigkeit getestet. Hauptaugenmerk lag dabei darauf, inwiefern sich Regeln, die über die Basisregeln aus Tabelle 3.4.1 hinausgehen, positiv auf die Anzahl der Transformationsschritte auswirken. Das Ergebnis ist beeindruckend: durch die Einführung komplexerer Transformationsregeln ließen sich in unseren Testfällen bis zu 87% der Transformationsschritte einsparen, im Durchschnitt immerhin noch 83%. Speziell komplexere Kontextmatchingprobleme mit einer größeren Anzahl an Kontextvariablen profitieren hiervon. Insbesondere die Erkennung korrespondierender Positionen in Verbindung mit der Regel Split führte zu erheblichen Verbesserungen. Die implementierten Algorithmen zur Erkennung korrespondierender Positionen stellen teilweise nur ein notwendiges Kriterium für die Existenz korrespondierender Löcher dar. Dies kann zu fehlerhaften Erkennungen solcher Positionen führen. Wie sich in unseren Tests zeigte, scheint das jedoch kein gravierendes Problem zu sein, da die entsprechenden Split- Transformationen ohnehin äußerst sparsam eingesetzt werden.
Work on proving congruence of bisimulation in functional programming languages often refers to [How89,How96], where Howe gave a highly general account on this topic in terms of so-called lazy computation systems . Particularly in implementations of lazy functional languages, sharing plays an eminent role. In this paper we will show how the original work of Howe can be extended to cope with sharing. Moreover, we will demonstrate the application of our approach to the call-by-need lambda-calculus lambda-ND which provides an erratic non-deterministic operator pick and a non-recursive let. A definition of a bisimulation is given, which has to be based on a further calculus named lambda-~, since the na1ve bisimulation definition is useless. The main result is that this bisimulation is a congruence and contained in the contextual equivalence. This might be a step towards defining useful bisimulation relations and proving them to be congruences in calculi that extend the lambda-ND-calculus.
Assessing enhanced knowledge discovery systems (eKDSs) constitutes an intricate issue that is understood merely to a certain extent by now. Based upon an analysis of why it is difficult to formally evaluate eKDSs, it is argued for a change of perspective: eKDSs should be understood as intelligent tools for qualitative analysis that support, rather than substitute, the user in the exploration of the data; a qualitative gap will be identified as the main reason why the evaluation of enhanced knowledge discovery systems is difficult. In order to deal with this problem, the construction of a best practice model for eKDSs is advocated. Based on a brief recapitulation of similar work on spoken language dialogue systems, first steps towards achieving this goal are performed, and directions of future research are outlined.
In the last decade, much effort went into the design of robust third-person pronominal anaphor resolution algorithms. Typical approaches are reported to achieve an accuracy of 60-85%. Recent research addresses the question of how to deal with the remaining difficult-toresolve anaphors. Lappin (2004) proposes a sequenced model of anaphor resolution according to which a cascade of processing modules employing knowledge and inferencing techniques of increasing complexity should be applied. The individual modules should only deal with and, hence, recognize the subset of anaphors for which they are competent. It will be shown that the problem of focusing on the competence cases is equivalent to the problem of giving precision precedence over recall. Three systems for high precision robust knowledge-poor anaphor resolution will be designed and compared: a ruleset-based approach, a salience threshold approach, and a machine-learning-based approach. According to corpus-based evaluation, there is no unique best approach. Which approach scores highest depends upon type of pronominal anaphor as well as upon text genre.
Die Darstellung photorealistischer Szenen durch Computer hat in Folge der Entwicklung immer effizienterer Algorithmen und leistungsfähigerer Hardware in den vergangenen Jahren gewaltige Fortschritte gemacht. Täuschend echt simulierte Spezialeffekte sind aus kaum einem Hollywood-Spielfilm mehr wegzudenken und sind zum Teil nur sehr schwierig als computergenerierte Bilder zu erkennen. Aufgrund der Komplexität von lebenden Organismen gibt es allerdings noch kein einwandfreies Verfahren, welches ein komplettes Lebewesen realistisch, sei es statisch oder in Bewegung, mit dem Computer simulieren kann. Im Bereich der Animation sind wirkungsvolle Resultate zu verzeichnen, da das Skelett eines Menschen oder Wirbeltieres durch geeignete Methoden simuliert und Bewegungen damit täuschend echt mit dem Computer nachgebildet werden können. Die Schwierigkeit, eine komplett realistische Visualisierung eines Lebewesens zu erreichen, liegt allerdings in der Darstellung weiterer Strukturen eines Organismus, die zwar nicht direkt sichtbar sind aber dennoch Einfluss auf die sichtbaren Bereiche haben. Bei diesen Strukturen handelt es sich um Muskel- und Fettgewebeschichten. Die Oberfläche von Figuren wird durch Muskeln sowohl in der Bewegung als auch in statischen Positionen deutlich sichtbar verändert. Dieser Effekt wird bisher bei der Visualisierung von Lebewesen nur unzureichend beachtet, was zu den aufgeführten nicht vollständig realistisch wirkenden Ergebnissen führt. Bei der Simulation von Muskeln wurden bis heute verschiedene Muskelmodelle entwickelt, die einen Muskel als Gesamtheit in Hinblick auf seine grundsätzlichen physikalischen Eigenschaften, wie z. B. Kraftentwicklung oder Kontraktionsgeschwindigkeit, sehr gut beschreiben. Viele Effekte des Muskels, die sich hauptsächlich auf einer tiefer liegenden Ebene abspielen, sind bis heute noch nicht erforscht, was folglich auch keine entsprechende Simulation auf dem Computer zulässt. Beschrieben werden die verschiedenen Muskeltypen (Skelett-, glatte und Herzmuskulatur) und Muskelformen (spindelförmige, einfach/doppelt gefiedert, etc.). Des weiteren wird auf die unterschiedlichen Muskelfasertypen (FTO, STO, usw.) mit ihren Eigenschaften und Funktionen eingegangen. Weitere Themen sind der strukturelle Aufbau eines Skelettmuskels, der Kontraktionsmechanismus und die Ansteuerung durch Nervenreize. Im Bereich Biomechanik, also der Forschung nach den physikalischen Vorgängen im Muskel, führte die Komplexität der Struktur und Funktionsweise eines Muskels zu einer ausgedehnten Vielfalt an Forschungsarbeiten. Zahlreiche Effekte, die bei einem arbeitenden Muskel beobachtet werden können, konnten bis heute noch nicht erklärt werden. Die Erkenntnisse, die für diese Arbeit relevant sind, sind jedoch in einem ausreichenden Maße erforscht und durch entsprechende mathematische Modelle repräsentierbar. Die Mechanik, die einem Muskel zugrunde liegt, wird auf diesen Modelle aufbauend beschrieben. Neben den Größen, die im später vorgestellten Modell verwendet worden sind, wird auch auf sonstige für biomechanische Untersuchungen relevante Eigenschaften eingegangen. Weiterhin wird dargestellt, wie verschiedene Kontraktionen (Einzelzuckung, Tetanus) mechanisch funktionieren. Für Muskelarbeit und Muskelleistung werden verschiedene Diagramme vorgestellt, welche die Zusammenhänge zwischen den physikalischen Größen Kraft, Geschwindigkeit, Arbeit und Leistung zeigen. Nach Vorstellung der ISOFIT-Methode zur Bestimmung von Muskel-Sehnen-Eigenschaften werden mathematische Formeln und Gleichungen zur Beschreibung von Kraft-Geschwindigkeits- und Kraft-Längen-Verhältnissen sowie der serienelastischen Komponente und der Muskelaktivierung, die zur Bewegungsgleichung führen, angegeben. Es folgen weitere mathematische Funktionen, welche die Aktivierungsvorgänge unterschiedlicher Muskelkontraktionen beschreiben, sowie das Muskelmodell nach Hill, welches seit vielen Jahren eine geeignete Basis für Forschungen im Bereich der Biomechanik darstellt. Bezüglich der Computergraphik wird ein kurzer Abriss gegeben, wie künstliche Menschen modelliert und animiert werden. Eine Übersicht über verschiedene Methoden zur Repräsentation der Oberfläche von Körpern, sowie deren Deformation unter Berücksichtigung der Einwirkung von Muskeln gibt die State-of-the-Art-Recherche. Neben den Oberflächenmodellen (Starrkörperdeformation, lokale Oberflächen-Operatoren, Skinning, Konturverformung, Deformation durch Keyshapes) werden auch Volumen- (Körperrepräsentation durch Primitive, Iso-Flächen) und Multi-Layer-Modelle (3-Layer-Modell, 4-Layer-Modell) vorgestellt und deren Vor- und Nachteile herausgearbeitet. Eine geeignete Repräsentation der Oberfläche, die Verformungen durch Muskelaktivität einbezieht, wurde durch die Benutzung von Pneus gekoppelt mit der Quaoaring-Technik gefunden. Dieses Verfahren, das auf Beobachtungen aus der Biologie basiert und zur Darstellung von organischen Körpern benutzt wird, ist ausgesprochen passend, um einen Muskel-Sehnen-Apparat graphisch darzustellen, handelt es sich doch hierbei auch um eine organische Struktur. Um die beiden Teilmodelle Simulation und Visualisierung zu verbinden, bietet sich die aus der Biomechanik bekannte Actionline an, die eine imaginäre Kraftlinie im Muskel und der Sehne darstellt. Die bei der Quaoaring-Methode verwendete Centerline, welches die Basis zur Modellierung des volumenkonstanten Körpers ist, kann durch die Kopplung an die physikalischen Vorgänge zu einer solchen Actionline erweitert werden. Veränderungen in der Länge und des Verlaufs der Actionline z. B. durch Muskelkontraktion wirken sich dadurch direkt auf die Form des Muskels aus und die Verbindung zur Visualisierung ist hergestellt.
RDF is widely used in order to catalogue the chaos of data across the internet. But these descriptions must be stored, evaluated, analyzed and verified. This creates the need to search for an environment to realize these aspects and strengthen RDFs influence. InterSystems postrelational database Caché exposes many features that are similar to RDF and provide persistence with semantic part. Some models for relational databases exist but these lack features like object-oriented data-structures and multidimensional variables. The aim of this thesis is to develop an RDF model for Caché that saves RDF data in an object-oriented form. Furthermore an interface for importing RDF data will be presented and implemented.
Robuste Anaphernresolution
(2004)
This paper proves correctness of Nocker s method of strictness analysis, implemented for Clean, which is an e ective way for strictness analysis in lazy functional languages based on their operational semantics. We improve upon the work of Clark, Hankin and Hunt, which addresses correctness of the abstract reduction rules. Our method also addresses the cycle detection rules, which are the main strength of Nocker s strictness analysis. We reformulate Nocker s strictness analysis algorithm in a higherorder lambda-calculus with case, constructors, letrec, and a nondeterministic choice operator used as a union operator. Furthermore, the calculus is expressive enough to represent abstract constants like Top or Inf. The operational semantics is a small-step semantics and equality of expressions is defined by a contextual semantics that observes termination of expressions. The correctness of several reductions is proved using a context lemma and complete sets of forking and commuting diagrams. The proof is based mainly on an exact analysis of the lengths of normal order reductions. However, there remains a small gap: Currently, the proof for correctness of strictness analysis requires the conjecture that our behavioral preorder is contained in the contextual preorder. The proof is valid without referring to the conjecture, if no abstract constants are used in the analysis.
It is shown that between one-turn pushdown automata (1-turn PDAs) and deterministic finite automata (DFAs) there will be savings concerning the size of description not bounded by any recursive function, so-called non-recursive tradeoffs. Considering the number of turns of the stack height as a consumable resource of PDAs, we can show the existence of non-recursive trade-offs between PDAs performing k+ 1 turns and k turns for k >= 1. Furthermore, non-recursive trade-offs are shown between arbitrary PDAs and PDAs which perform only a finite number of turns. Finally, several decidability questions are shown to be undecidable and not semidecidable.