Informatik
Refine
Year of publication
Document Type
- Preprint (759)
- Article (402)
- Working Paper (119)
- Doctoral Thesis (93)
- Diploma Thesis (47)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (36)
- diplomthesis (28)
- Report (25)
Has Fulltext
- yes (1619)
Is part of the Bibliography
- no (1619)
Keywords
Institute
- Informatik (1619)
- Frankfurt Institute for Advanced Studies (FIAS) (1008)
- Physik (986)
- Mathematik (56)
- Präsidium (41)
- Medizin (25)
- Biowissenschaften (21)
- Exzellenzcluster Makromolekulare Komplexe (8)
- Psychologie (8)
- Deutsches Institut für Internationale Pädagogische Forschung (DIPF) (5)
- Geowissenschaften (5)
- Senckenbergische Naturforschende Gesellschaft (5)
- Biochemie und Chemie (4)
- Geographie (4)
- Hochschulrechenzentrum (4)
- Pharmazie (4)
- Goethe-Zentrum für Wissenschaftliches Rechnen (G-CSC) (3)
- Universitätsbibliothek (3)
- Biodiversität und Klima Forschungszentrum (BiK-F) (2)
- Center for Membrane Proteomics (CMP) (2)
- Institut für Ökologie, Evolution und Diversität (2)
- Sportwissenschaften (2)
- Wirtschaftswissenschaften (2)
- Center for Scientific Computing (CSC) (1)
- E-Finance Lab e.V. (1)
- Erziehungswissenschaften (1)
- Geschichtswissenschaften (1)
- Gesellschaftswissenschaften (1)
- Informatik und Mathematik (1)
- Institut für Bienenkunde (1)
- Kulturwissenschaften (1)
- MPI für Biophysik (1)
- Neuere Philologien (1)
- Zentrum für Arzneimittelforschung, Entwicklung und Sicherheit (ZAFES) (1)
- Zentrum für Weiterbildung (1)
The thesis in general deals with CORBA, the Common Object Request Broker Architecture. More specifically, it takes a look at the server-side, where object adapters exist to aid the developer in implementing objects and in dealing with request processing. The new Portable Object Adapter was recently added to the CORBA 2.2 standard. My task was the implementation of the POA in MICO and the examination if (a) the POA specification is sensible and (b) in which areas it improves over the old Basic Object Adapter. After introducing distributed platforms in general and CORBA in particular, the thesis' main two chapters are a detailed abstract examination ("Design") of the POA design and their relization ("Implementation"), highlighting the potential trouble spots, persistence and collocation.
We present the FPGA implementation of an algorithm [4] that computes implications between signal values in a boolean network. The research was performed as a masterrsquos thesis [5] at the University of Frankfurt. The recursive algorithm is rather complex for a hardware realization and therefore the FPGA implementation is an interesting example for the potential of reconfigurable computing beyond systolic algorithms. A circuit generator was written that transforms a boolean network into a network of small processing elements and a global control logic which together implement the algorithm. The resulting circuit performs the computation two orders of magnitudes faster than a software implementation run by a conventional workstation.
This paper presents a new timing driven approach for cell replication tailored to the practical needs of standard cell layout design. Cell replication methods have been studied extensively in the context of generic partitioning problems. However, until now it has remained unclear what practical benefit can be obtained from this concept in a realistic environment for timing driven layout synthesis. Therefore, this paper presents a timing driven cell replication procedure, demonstrates its incorporation into a standard cell placement and routing tool and examines its benefit on the final circuit performance in comparison with conventional gate or transistor sizing techniques. Furthermore, we demonstrate that cell replication can deteriorate the stuck-at fault testability of circuits and show that stuck-at redundancy elimination must be integrated into the placement procedure. Experimental results demonstrate the usefulness of the proposed methodology and suggest that cell replication should be an integral part of the physical design flow complementing traditional gate sizing techniques.
In der vorliegenden Diplom-Arbeit wurde das in [19] vorgeschlagene Modell zur Partitionierung hybrider Systeme diskutiert und die Anwendbarkeit verschiedener verschiedener Optimierungsverfahren auf das Problem untersucht.
Hierbei wurde der Systemgraph um die Ein-/Ausgabe-Blöcke erweitert, damit der Systemgraph eine eine konsistente Erweiterung des des Graphen-Modells darstellt. Weiterhin wurden die Probleme und Einschränkungen aufgezeigt, die sich bei der Abbildung eines hybriden Systems auf den Systemgraphen ergeben.
Gegenstand der Arbeit ist ein Gleichheitskalkül für den Kern einer nicht-strikten funktionalen Programmiersprache. Funktionale Programmiersprachen unterstützen bestens die Prinzipien Abstraktion, Einkapselung, Hierarchiesierung und Modularisierung, die gemeinhin als Grundelemente des Software-Engineering betrachtet werden. Darüber hinaus bieten funktionale Programmiersprachen aufgrund ihrer Entwicklung aus dem Lambda-Kalkül eine große Nähe zu mathematischen Modellen. Daher besitzen sie im Bereich der Programmverifikation ausgeprägte Vorteile gegenüber imperativen oder objekt-orientierten Programmiersprachen. In der Arbeit wird nun ein Gleichheitsbegriff für Ausdrücke in funktionalen Programmiersprachen entwickelt und dessen Praktikabilität durch die Implementierung eines Beweisers untermauert. Dieser Gleichheitsbegriff ist die kontextuelle Gleichheit, die Ausdrücke aufgrund ihres Terminierungsverhaltens als Unterprogramme in allen möglichen Kontexten einordnet. Kontextuelle Gleichheit wird in Kapitel 2 vorgestellt, nachdem der klassische und der sogenannte "lazy" Lambda-Kalkül eingeführt wurden. Kapitel 3 enthält einen Überblick über die funktionale Programmierung, da auch die Implementierung des o.g. Beweisers in einer funktionalen Programmiersprache, nämlich Haskell, durchgeführt wird. In Kapitel 4 wird die funktionale Kernsprache, die Gegenstand der Untersuchung sein wird, beschrieben. Sie enthält alle wesentlichen Elemente wie z.B. Funktionsdefinition und -anwendung sowie Datentypen. Im selben Kapitel wird auch der Gleichheitsbegriff für diese Kernsprache definiert. Kapitel 5 schließlich entwickelt auf Basis der zuvor erfolgten Definitionen einen Kalkül für den Gleichheitsbeweis. Außerdem wird in diesem Kapitel auch die Umsetzung dieses Gleichheitskalküls präsentiert. Aus der Dissertation von Marko Schütz werden hierbei Erkenntnisse über die Kontextanalyse verwendet, um erfüllende Belegungen von freien Variablen zu berechnen. Die Arbeit schließt mit Beispielanalysen und Meßwerten sowie einer Diskussion der Ergebnisse und möglicher Erweiterungen.
Wir betrachten in dieser Diplomarbeit die Sicherheit des ringbasierten Public Key Kryptosystems NTRU, das 1996 von J. Hoffstein, J. Pipher und J.H. Silverman vorgeschlagen wurde. Dieses Kryptosystem bietet schnelle Kodierung und Dekodierung in Laufzeit O(n exp 2) bei kleinem Sicherheitsparameter n. Die Sicherheit des Systems beruht auf einem Polynomfaktorisierungsproblem (PFP)im Polynomring Zq[X]/(X exp n -1). Das PFP wurde von Coppersmith und Shamir auf ein Kürzestes Vektor Problem im Gitter Lcs reduziert. Die neuen Ergebnisse dieser Arbeit bauen auf dem Gitter Lcs auf. Wir betrachten die Nachteile von Lcs und konstruieren verbesserte Gitterbasen zum Angriff auf das NTRU-Kryptosystem. Dabei nutzen wir Strukturen des Polynomrings Zq[X]/(X exp n -1) und der geheimen Schlüssel aus. Durch die neuen Gitterbasen wird der Quotient aus der Länge des zweitkürzesten und der Länge des kürzesten Gittervektors vergrößert. Da wir Approximationsalgorithmen zum Finden eines kürzesten Vektors verwenden, beschleunigt dies die Attacken. Wir präsentieren verschiedene Methoden, wie man die Dimension der Gitterbasen verkleinern kann. Durch die verbesserten Gitterattacken erhalten wir eine Cryptanalyse des NTRU-Systems in der vorgeschlagenen mittleren Sicherheitsstufe. Beträgt die Zeit zum Brechen eines Public-Keys unter Verwendung der Coppersmith/Shamir-Basis 1 Monat, so verringert sich die Laufzeit durch einen kombinierten Einsatz der neuen Gitterbasen auf ca. 5 Stunden auf einem Rechner und bei Parallelisierung auf ca. 1:20 Stunde auf 4 Rechnern. Wir erwarten, daß die neuen Methoden NTRU in hoher Sicherheitsstufe n = 167 brechen, obwohl für dieses n bisher nur "schwache" Schlüssel gebrochen wurden. Trotz signifikanter Verbesserungen deuten die experimentellen Ergebnisse auf ein exponentielles Laufzeitverhalten bei steigendem Sicherheitsparameter n hin. Der Laufzeitexponent kann allerdings gesenkt werden, so daß man n größer wählen muß, um Sicherheit gegenüber den neuen Attacken zu erzielen. Auch wenn das NTRU-Kryptosystem nicht vollständig gebrochen wird, verliert es seinen größten Vorteil gegenüber anderen Public Key Kryptosystemen: Die effiziente Kodierung und Dekodierung bei kleinem Sicherheitsparameter n.
In this paper we regard first the situation where parallel channels are disturbed by noise. With the goal of maximal information conservation we deduce the conditions for a transform which "immunizes" the channels against noise influence before the signals are used in later operations. It shows up that the signals have to be decorrelated and normalized by the filter which corresponds for the case of one channel to the classical result of Shannon. Additional simulations for image encoding and decoding show that this constitutes an efficient approach for noise suppression. Furthermore, by a corresponding objective function we deduce the stochastic and deterministic learning rules for a neural network that implements the data orthonormalization. In comparison with other already existing normalization networks our network shows approximately the same in the stochastic case but, by its generic deduction ensures the convergence and enables the use as independent building block in other contexts, e.g. whitening for independent component analysis. Keywords: information conservation, whitening filter, data orthonormalization network, image encoding, noise suppression.
This paper describes the problems and an adaptive solution for process control in rubber industry. We show that the human and economical benefits of an adaptive solution for the approximation of process parameters are very attractive. The modeling of the industrial problem is done by the means of artificial neural networks. For the example of the extrusion of a rubber profile in tire production our method shows good results even using only a few training samples.
The encoding of images by semantic entities is still an unresolved task. This paper proposes the encoding of images by only a few important components or image primitives. Classically, this can be done by the Principal Component Analysis (PCA). Recently, the Independent Component Analysis (ICA) has found strong interest in the signal processing and neural network community. Using this as pattern primitives we aim for source patterns with the highest occurrence probability or highest information. For the example of a synthetic image composed by characters this idea selects the salient ones. For natural images it does not lead to an acceptable reproduction error since no a-priori probabilities can be computed. Combining the traditional principal component criteria of PCA with the independence property of ICA we obtain a better encoding. It turns out that the Independent Principal Components (IPC) in contrast to the Principal Independent Components (PIC) implement the classical demand of Shannon’s rate distortion theory.
This paper proposes a new approach for the encoding of images by only a few important components. Classically, this is done by the Principal Component Analysis (PCA). Recently, the Independent Component Analysis (ICA) has found strong interest in the neural network community. Applied to images, we aim for the most important source patterns with the highest occurrence probability or highest information called principal independent components (PIC). For the example of a synthetic image composed by characters this idea selects the salient ones. For natural images it does not lead to an acceptable reproduction error since no a-priori probabilities can be computed. 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.
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.
In dieser Arbeit definieren wir ein Maß für den Grad der Mehrdeutigkeit (degree of ambiguity da) kontextfreier Grammatiken und Sprachen als die Anzahl der Ableitungsbäume in Abhängigkeit von der Länge n eines Wortes. Wir zeigen, dass es weder Sprachen noch zyklenfreie Grammatiken gibt, deren Mehrdeutigkeitsgrad stärker als 2£(n) wächst (wie z B. £(nn)). Aus [10] ist es außerdem bekannt, dass es keine Grammatiken (und somit keine Sprachen) gibt, deren Mehrdeutigkeit stärker als polynomiell, aber schwächer als exponentiell wächst (wie z. B. £(2pn). Deshalb untersuchen wir in dieser Arbeit hauptsächlich konstant mehrdeutige, polynomiell mehrdeutige und exponentiell mehrdeutige Grammatiken und Sprachen. Für jede feste, ganze Zahl k 2 N hat Maurer [8] die Existenz einer k-deutigen kontextfreien Sprache nachgewiesen. Durch Verwendung einer einfacheren Sprache, nämlich der Sprache Lk := fambm1 1 bm2 2 : : : bmk k jm;m1;m2; : : : ;mk ¸ 1; 9 i mit m = mig, und mit Hilfe von Ogden's Lemma1 erhalten wir einen wesentlich kürzeren Beweis. Ferner zeigen wir die Existenz exponentiell mehrdeutiger Sprachen. Wir zeigen, dass die Sprache L¤ { wobei L = faibicj ji; j ¸ 1g [ faibjciji; j ¸ 1g-exponentiell mehrdeutig ist, indem wir beweisen, dass das Wort (ah+h!bh+h!ch+h!)k mindestens 2k Ableitungen in jeder Grammatik G für L¤ hat, wobei k aus N ist und h die Konstante aus Ogden's Lemma für G ist. Für beliebig kleines c aus R+ entwerfen wir eine Grammatik Gc für L¤, so dass daGc · 2cn gilt. Somit gilt, dass die Sprache L¤ zwar exponentiell mehrdeutig ist, aber es gibt kein festes c aus R+ , so dass L¤ 2cn-deutig ist. Wir geben polynomiell mehrdeutige Grammatiken an und zeigen die Existenz von polynomiell mehrdeutigen Sprachen, indem wir mit Hilfe von Ogden's Lemma beweisen, dass die Anzahl der Ableitungsbäume eines Wortes der Länge n in jeder Grammatik für die Sprache Lk in der Größenordnung von (nk) liegt, wobei k eine Konstante aus N ist, und L := fambm1cbm2c : : : bmpcjp 2 N; m;m1;m2; : : : ;mp 2 N; 9i 2 f1; 2; : : : ; pg mit m = mig gilt. Durch Angabe einer O(nk){deutigen Grammatik zeigen wir schließlich, dass Lk polynomiell vom Grad k mehrdeutig ist. Außerdem entwerfen wir für jedes feste d aus R+ eine Grammatik Gd für L, so dass daGd · dn dn für genügend großes n ist.
In this paper we present a non-deterministic call-by-need (untyped) lambda calculus lambda nd with a constant choice and a let-syntax that models sharing. Our main result is that lambda nd has the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambdalifting using deterministic maximal free expressions. These results show that lambda nd is a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation. An intended application of lambda nd is as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
A und B möchten digitale Unterschriften auf faire Weise austauschen, d.h. A soll genau dann eine Unterschrift von B erhalten, wenn B eine Unterschrift von A erhält. Der triviale Ansatz zum Austausch zweier Unterschriften, daß A seine Unterschrift an B sendet und dann B seine Unterschrift an A schickt, ist nicht fair, da B nach Erhalt der Unterschrift von A das Protokoll vorzeitig beenden oder eine ungültige Unterschrift senden kann. Bei den bekannten praktikablen Protokollen zum fairen Austausch unterteilen die Teilnehmer die Unterschriften in kleine Blöcke aus wenigen Bits und tauschen die Blöcke dann schrittweise aus. Diese Protokolle garantieren einerseits, daß man sofort überprüfen kann, ob ein erhaltener Block korrekt ist. Andererseits geben die bereits ausgetauschten Blöcke so wenig wie möglich über den restlichen Teil der Unterschrift preis. Versucht in diesem Fall ein Teilnehmer zu betrügen, indem er beispielsweise einen falschen Wert sendet, so kann der andere Teilnehmer dies unmittelbar bemerken und stoppen. Da die noch nicht ausgetauschten Blöcke fast nichts über den übrigen Teil der Unterschrift preisgeben, hat der Betrüger höchstens einen Block mehr als der ehrliche Teilnehmer erhalten. Ist die Blockgröße hinreichend klein, kann der ehrliche Teilnehmer den Nachteil durch Raten bzw. Probieren ausgleichen. In dieser Diplomarbeit entwickeln wir Protokolle zum fairen Austausch sogenannter Diskreter- Logarithmus-Unterschriften. Die bekannten praktikablen Protokolle zum Austausch dieses Unterschriftentyps verwenden als Sicherheitsvoraussetzung die Faktorisierungsannahme. Im Unterschied dazu beruht die Sicherheit unseres Austauschprotokolls auf der Diskreten- Logarithmus-Annahme und damit auf der des Unterschriftenverfahrens. Ferner erlauben unsere Protokoll die Herausgabe der Blöcke in beliebiger, auch vom Protokollverlauf abhängiger Reihenfolge, während die Reihenfolge bei den bisherigen Protokollen von vornherein festgelegt ist.
Um in verschiedenen Anwendungsumgebungen eingesetzt werden zu können, lässt die CORBA-Spezifikation einen weiten Spielraum für Implementierungen. Sollte CORBA in einem speziellen Umfeld eingesetzt werden, so war bisher eine Neu-Implementierung notwendig, da herkämmliche CORBA-Implementierungen nicht oder nur sehr eingeschränkt an spezielle Anwendungsumgebungen anpassbar sind. In dieser Arbeit wurde ein Ansatz für eine erweiterbare CORBA-Implementierung vorgestellt und implementiert.
A new approach to optimize multilevel logic circuits is introduced. Given a multilevel circuit, the synthesis method optimizes its area while simultaneously enhancing its random pattern testability. The method is based on structural transformations at the gate level. New transformations involving EX-OR gates as well as Reed–Muller expansions have been introduced in the synthesis of multilevel circuits. This method is augmented with transformations that specifically enhance random-pattern testability while reducing the area. Testability enhancement is an integral part of our synthesis methodology. Experimental results show that the proposed methodology not only can achieve lower area than other similar tools, but that it achieves better testability compared to available testability enhancement tools such as tstfx. Specifically for ISCAS-85 benchmark circuits, it was observed that EX-OR gate-based transformations successfully contributed toward generating smaller circuits compared to other state-of-the-art logic optimization tools.
Im Zeitraum 1. 11. 1993 bis 30. 3. 1997 wurden 1149 allgemeinchirurgische Intensivpatienten prospektiv erfaßt, von denen 114 die Kriterien des septischen Schocks erfüllten. Die Letalität der Patienten mit einem septischen Schock betrug 47,3%. Nach Training eines neuronalen Netzes mit 91 (von insgesamt n = 114) Patienten ergab die Testung bei den verbleibenden 23 Patienten bei der Berücksichtigung von Parameterveränderungen vom 1. auf den 2. Tag des septischen Schocks folgendes Ergebnis: Alle 10 verstorbenen Patienten wurden korrekt als nicht überlebend vorhergesagt, von den 13 Überlebenden wurden 12 korrekt als überlebend vorhergesagt (Sensitivität 100%; Spezifität 92,3%).
Durch zunehmende Vernetzung steigt auch das Interesse elektronische Wahlen mit Hilfe kryptographischer Methoden auf Rechnernetzen zu verwirklichen. In der folgendern Arbeit werden Wahlschemata behandelt, deren Ziel es ist, die gesamte Wahl auf einem Rechnernetz durchzuführen. Die Arbeit beschränkt sich auf Wahlen mit zwei Wahlvorschlägen. Auf Wahlen mit drei oder mehr Wahlvorschlägen wird nicht eingegangen. Im ersten Kapitel wird eine Einleitung in die elektronischen Wahlen gegeben. Im zweiten Kapitel wird das verwendete Modell eines Wahlschemas und die Anforderungen, bezüglich der die Wahlschemata untersucht werden, vorgestellt. Im dritten Kapitel werden die kryptographische Methoden für die folgenden Kapitel vorgestellt. Im vierten Kapitel werden zwei Wahlschemata betrachtet, deren Ansatz es ist, die Stimmen mit Hilfe von Schwellenwerten auf mehrere Behörden zu verteilen. Die Sicherheit der Wahlschemata in diesem Kapitel basiert auf dem diskreten Logarithmus. Im fünften Kapitel werden weitere Wahlschemata betrachet, bei denen die Wähler mit Hilfe von Verschlüsselungsmethoden ihre Stimmen an die Behörden senden. Die Sicherheit dieser Schemata basiert auf dem Wurzelziehen modulo einer zusammengesetzten Zahl mit unbekannter Faktorisierung. In diesem Kapitel lernen wir auch das erste quittungsfreie Wahlschema kennen. Im sechsten Kapitel werden Wahlschemata betrachtet, die das Konzept eines Mixes benutzen. Auch in diesem Kapitel lernen wir ein quittungsfreies Wahlschema kennen.
Funktionsorientierte Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen
(1997)
Das Ziel der vorliegenden Arbeit war die Entwicklung einer komfortablen Beschreibung verteilter Anwendungen, die kontinuierliche Medien integrieren. Die Klarheit des Ansatzes ergibt sich aus der Beschränkung auf die anwenderrelevanten Funktionalitäten. Weitere Gebiete, die systembezogen sind, wurden nur soweit wie nötig behandelt. Die Aufgaben anderer Bereiche, wie des Betriebssystems und des Managementsystems sowie der Kommunikationsdienste, konnten nur gestreift werden, indem die anwendungsabhängigen Anforderungen spezifiziert wurden. Durch deren Extraktion und die Zuordnung der Anforderungen an die einzelnen Bereiche, ergibt sich eine klarere Sicht auf Betriebssystem, Management und Kommunikationsdienste und deren notwendige Weiterentwicklung. Das entwickelte Funktionenmodell beschreibt zusammenhängend alle mit kontinuierlichen Medien verbundenen Arbeiten. In der vorliegenden Arbeit wurde gezeigt, wie aus den Funktionen auf kontinuierlichen Medien durch die Spezifikation geeigneter Schnittstellen Bausteine zur Integration der Medien in verteilte Anwendungen erstellt werden. Die Beschrei bung der Bausteine erfolgt durch diese Schnittstellen; es sind Steuer-, Daten- und Managementschnittstellen. Die Herauslösung der gesonderten Beschreibung der Multimedia-Datenflußstruktur schafft einerseits die Grundlage für eine Teilklassifikation der Anwendungen nach Medien-Gesichtspunkten. Andererseits kann die Erstellung einer Anwendung aus einer bestimmten Anwendungsklasse, wie zum Beispiel ein einfaches Wiedergabesystem, durch die gesonderte Beschreibung der Multimedia-Datenflußstruktur schneller in der Bausteinstruktur realisiert werden. Das Funktionenmodell wird auch in [Fritzsche96] beschrieben. Das in dieser Arbeit konzipierte Bausteinmodell gewährleistet eine integrierte Beschreibung von Geräten, Werkzeugen und Anwendungen kontinuierlicher Medien. Die verwendete Beschreibungstechnik erlaubt dabei nicht nur eine übersichtliche Darstellung sondern bietet auch hierarchische Strukturierungen an. Das Zusammenspiel der Bausteine erfordert zu sätzliche Komponenten zur Steuerung und Abstimmung der einzelnen Funktionen, die in dieser Arbeit neu eingeführt werden. Es lassen sich sowohl zentralistische als auch verteilte Steuerungen realisieren. Mit einer entsprechenden Schnittstelle versehen kann eine Steuerkomponente eine ganze Gruppe von Bausteinen dem Benutzer als Einheit zur Verfügung stellen. Somit lassen sich auch verschiedene Medien und/oder mehrere Funktionen gemeinsam mit einer Steuerkomponente zu einem Baustein zusammenfassen. Diese zusammenge setzten Bausteine bieten nun echte Multifunktionalität und Multimedialität. Durch die Komponenten- und Anwendungsmodellierung nach [Zimm93] wird darüber hinaus eine flexible, auch dynamisch änderbare Anwendungsstruktur vom Anwendungs-Management ermöglicht. Das Bausteinmodell wird auch in [Fritzsche96] behandelt. Bisherigen Ansätzen für Multimedia-Komponenten fehlt die allgemeine Interoperabilität der Komponenten. Diese kann nur durch eine umfassende, formale Spezifikation der Komponenten-Schnittstellen, insbesondere aber von Steuerschnittstellen, erfolgen. Zur Spezifikation der Schnittstellen ist die Integration der kontinuierlichen oder zeitabhängigen Medien als abstrakte Datentypen unabdingbar. Auf diese Art werden aus den Komponenten Bausteine. Im vorliegenden Ansatz wurden erstmalig Steuerschnittstellen für Multimedia-Komponenten spezifiziert und als Hierarchie dargestellt. Der neue Ansatz erlaubt es daher, multimediale Systeme nach einem Baukastensystem zu erstellen, indem Bausteine durch Bindung untereinander zu einer Anwendung zusammengesetzt werden. Nach der Verbindungsstruktur der multimedialen Anwendung können verschiedene Anwendungstypen unterschieden werden. Die Definition der Komponentenschnittstellen bezieht sich auf ein abstraktes Datenmodell für kontinuierliche Medien. Das Datenmodell ist eine eigenständige Weiterentwicklung der Ansätze von [Herrtw91] und [Gibbs94] und kann auch zur Realisierung der Komponenten verwendet werden. Multimediadaten wurden zunächst auf zwei Ebenen als Sequenz und Sequenzelemente modelliert. Daraus lassen sich bereits einige Funktionen auf den Daten ableiten, die von den Bausteinen realisiert werden müssen. Kennzeichnend für die Sequenzelemente ist, daß sie die Zeitparameter Zeitpunkt und Dauer besitzen und damit eine explizite Integration der Zeit in das Datenmodell realisieren. Aus diesen Parametern der Elemente können auch für die Sequenz die Parameter Zeitpunkt und Dauer abgeleitet werden. Somit könnte eine Sequenz selbst wieder Element einer Sequenz werden. Da diese Sequenzen von Sequenzen aber zum Teil schwer zu handhaben sind und zum Aufbau von sehr komplexen Verschachtelungen verleiten, wird in dieser Arbeit eine andere Erweiterung der Datenhierarchie, eine Liste, vorgestellt. Diese Erweiterung führt nur eine weitere Hierarchieebene oder Granularitätsstufe ein, ist aber durch die vorgegebenen Funktionen gleichmächtig wie die Verschachtelung der Sequenzen, im Operationsablauf aber leichter nachzuvollziehen. Die Liste repräsentiert die gröbste Granularitätsstufe. Diese ist mit der Titelfolge einer Schallplatte oder einer CD vergleichbar. Die einzelnen Teile haben zueinander nur eine lose Ordnung. In der ersten Verfeinerung der Granularität wird in jedem einzelnen Listenelement eine strenge zeitliche Ordnung gefordert; ein Listenelement ist eine Sequenz. In der zweiten Stufe der Verfeinerung, der Unterteilung der Sequenzen, treten die bereits bekannten Se quenzelemente auf. Die Daten werden im Ticker-Schrittgeber-Modell interpretiert. Dieses Modell erhält zwei Zeitebenen, den Ticker als Bezugssystem der Funktionen untereinander und den Schrittgeber als Steuerung der einzelnen Funktionen. Ein zweistufiges Uhrenmodell mir festgesetzten Operationen und Uhrenbeziehungen wird in dieser Arbeit neu eingeführt. Die Beziehung zwischen Schrittgeber und Ticker ist, daß ein Schritt nach einer bestimmten Anzahl von Ticks erfolgt. Der Startwert des Tickers kann frei gewählt werden, ebenso der Startwert des Schrittgebers. Für den Schrittgeber bestimmt sein Start-Tick, wann er beginnt fortzuschreiten. Ein Schrittgeber ist mit genau einer Sequenz verbunden, deren Start-Schritt beschreibt, bei welchem Schrittwert das erste Sequenzelement gültig wird. Die Start-Zeitpunkte der Elemente und ihre Dauern werden in Schritten gemessen. Das Datenmodell für Multimedia wurde in [Fritzsche95] veröffentlicht. Implementierungen Als Grundlage für die Entwicklung der Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen wurden die Funktionen auf den Medien herangezogen. Diese sind in ihren einfachsten Formen die Grundfunktionen Perzeption, Präsentation und Speicherung der Medien, wobei die Speicherung in die Funktionen Schreiben in den Speicher und Lesen aus dem Speicher geteilt wird. Die durch die Perzeption festgelegten, oder künstlich erzeugten Mediendaten können zwischen den einzelnen Funktionen übertragen werden. Eine Bearbeitung der Daten ist beim Austausch zwischen den Funktionen möglich. Die Veränderung der Daten und ihr Bezug zu den Grundfunktionen wird durch die Verarbeitungsfunktionen der Typen f 1 bis f 5 beschrieben. Die Funktionen werden durch Operationen gesteuert, die aus dem Datenmodell abgeleitet werden. Insbesondere wird so auch die explizite Veränderung der Zeitparameter möglich. Somit bietet das Datenmodell eine geeignete Grundlage für jede Art der Verarbeitung kontinuierlicher Medien. Das entwickelte Modell unterstützt die Anwendungserstellung durch objektorientierte Ansätze auf den Ebenen der Konzeption, der Anwendungsspezifikation und der Komponentenentwicklung. Konzeptionell bietet das Funktionenmodell die schnelle und übersichtliche Darstellung der Anwendung. Die aus dem Funktionenmodell ableitbare Anwendungsspezifikation unterstützt die weitere Entwicklung durch Anwendungs- und Komponentenschablonen, sowie durch die vorgefertigte und erweiterbare Hierarchie der Schnittstellen und durch die Bibliotheken für Standardbausteine. Die Verwendung dieser Elemente der Anwendungsspezifikation läßt sich teilweise automatisieren. Das Ergebnis der Anwendungsspezifikation ist eine Menge von Komponenten, die alle vollständig spezifiziert sind. Diese Komponenten sind die funktionsorientierten Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen. Im ersten Schritt wurde das vorgestellte Datenmodell mit seinen Operationen in einer objektorientierten Programmiersprache (C [Lipp91]) implementiert [Braun92]. Darauf aufbauend wurden verschiedene Anwendungsfunktionen und Normalisierungsoperationen entwickelt und für den Bereich Audio realisiert [Bast93]. Die von den Funktionen auf kontinuierlichen Medien abgeleiteten Bausteine werden, wie in der vorliegenden Arbeit ausführlich dargestellt, als Komponenten verteilter Anwendungen realisiert. Aus den verschiedenen Realisierungsebenen sollen hier zwei Beispiele hervorgehoben werden. Zunächst wird auf die Komponentenrealisierung eingegangen; danach folgt die Realisierung von Tickern und enger Kopplung. Diese beiden Punkte stellen zentrale Aufgaben des Ansatzes dar. Realisierung von Komponenten Die Realisierung der Komponenten gliedert sich in zwei Abschnitte. Der erste Abschnitt ist die Zerlegung einer Komponente in Standardobjekte nach [Zimm93]. Die Standardobjekte entstammen Kommunikationsklassen, Stub- und Dispatcherklassen, Anwendungsklassen und Kooperationsprotokollklassen. Die Objekte der Anwendungsklassen realisieren die Anwendungsfunktionalität der Komponente. Das Ausprogrammieren dieser Objekte stellt den zweiten Abschnitt der Komponentenrealisierung dar. Dazu liefert das entwickelte Datenmodell die Programmierunterstützung. Zur Abbildung der Spezifikationskonstrukte der Komponenten auf Implementierungskonstrukte wird in [Zimm93] eine Methode vorgestellt, die die unterschiedlichen Konstrukte für Schnittstellen, Kommunikationskontexte und Komponenten auf Klassen und Objekte abbildet. So entsteht eine Klassenhierarchie von C Klassen [Lipp91] für kommunikations-, anwendung-s und managementorientierte Objekte. Weiterhin wird in [Zimm93] ein Verfahren vorgestellt, durch das in Abhängigkeit von den Eigenschaften einer Komponente parallel ablaufende Datenflüsse in ein System von leichtgewichtigen Prozessen (Threads) transformiert werden können. Als Resultat gewinnt man eine modulare Softwarearchitektur der Komponente, die sich aus interagierenden Objekten und zugehörigen Threads zusammen setzt. In [Zimm93] werden folgende Objektklassen unterschieden: . Kommunikationsklassen . Stub- und Dispatcherklassen . Anwendungsklassen . Kooperationsprotokollklassen. Eine elementare Objektarchitektur aus diesen Klassen ist in Abbildung 54 dargestellt. Es gibt jeweils eine Realisierung für eine Supplier-Komponente und eine Consumer- Komponente. Die Anwendungsobjekte können bezüglich ihrer Funktionalität in initiierende und akzeptierende Objekte eingeteilt werden. Im Falle unidirektionaler Schnittstellen sind die Anwendungsobjekte auf der Konsumentenseite (z.B. Benutzerkomponente) für die Initiierung von Methoden an Schnittstellenobjekten verantwortlich. Beispielsweise ist ein Anwendungsobjekt innerhalb der Benutzerkomponente für die Initiierung der Steueroperationen verantwortlich. Im Falle von interaktiven Komponenten [Zimm93] erfolgt dazu ein Benutzerdialog mit einem interaktiven Benutzer. Also realisiert innerhalb der Benutzerkomponente das Anwendungsobjekt einen solchen Benutzerdialog. Anwendungsobjekte auf der Konsumentenseite stellen somit typischerweise keine eigenen Methoden bereit, sondern bestehen lediglich aus einem Konstruktor. Auf der akzeptierenden Seite, den Anbieter (Supplier), realisiert ein Anwendungsobjekt die Operationen an einer Schnittstelle. Dazu wird eine Methode accept benötigt, falls ein verbindungsorientierter Kommunikationskontext zugrunde liegt. Diese Methode dient der Behandlung eingehender Verbindungswünsche. In [Alireza94] werden verschiedene Komponentenrealisierungen ausführlich vorgestellt. Die Realisierung der Ticker und Schrittgeber stellt die Einbettung der zeitbezogenen Komponenten in ihre (Betriebssystem) Umgebung dar. Ähnlich, wie eine Komponente über den Socketmechanismus Zugang zum Kommunikationssystem erhält, erhält eine zeitbezogene Komponente über den Ticker-Schrittgeber-Mechanismus Zugang zum Zeitbezugssystem. Denn die Schrittgeber beziehen sich auf Ticker, Ticker aber auf die Systemzeit. Da auch die Systemzeit als Takt zur Verfügung gestellt wird, können Ticker und Schrittgeber wegen ihrer ähnlichen Funktionalitäten aus einer gemeinsamen Zeitgeberklasse abgeleitet werden. Im Anhang C ist die Deklaration dieser gemeinsamen Klasse angegeben. In einer Anwendung beziehen sich die Schrittgeber verschiedener Komponenten auf einen gemeinsamen Ticker. Dieser Ticker liegt in der Systemumgebung der den Komponenten gemeinsamen interaktiven Benutzerkomponente. Die interaktive Benutzerkomponente verteilt die Ticks über die Steuerschnittstellen an die Komponenten und realisiert so die enge Kopplung der Komponenten. Bei einer Tickrate von 600 Hz ist es nur innerhalb eines Systems sinnvoll jeden Tick als Ereignis zu verteilen. Anstatt nun zu jedem Tick ein Ereignis zu verteilen werden bei der Tickverteilung Tickwerte mit fester Rate verteilt, wobei diese Rate in die Größenordnung der Schritte fällt. Um die Übertragungsraten gemäß den Anforderungen an der Steuerschnittstelle klein zu halten, wird zu jedem Schritt nur ein Teil (1 Byte) des Tickwertes übertragen. Begonnen wird mit der Übertragung des höchstwertigen Bytes, so daß im letzten Schritt einer Tickerübertragung mit dem letzten Byte der genaue aktuelle Tickwert übertragen wird. Ähnliche Verfahren werden bereits bei anderen Synchronisations verfahren verwendet. Eine genaue Beschreibung sowie die Kodierung für die verschachtelte Übertragung von Tickwerten und SchnittstellenAufrufen wird in [Hesme93] vorgestellt. Weitere Entwicklung Zur Realisierung verteilter multimedialer Anwendungen, muß man die einzelnen verteilten Komponenten bestimmen und ihre Funktion beschreiben. Die Komponenten tauschen unter einander Steuerungsinformationen und Multimediadaten aus. Diese Daten und das beim Austausch verwendete Protokoll sollten allgemein standardisiert sein, um den Zusammen schluß heterogener Systeme zu ermöglichen. In der vorliegenden Arbeit wurde gezeigt, wie sowohl die Daten als auch das Zusammenspiel der Komponenten festgelegt werden können. Obwohl alle Geräteklassen und Geräte funktionen sowie verschiedene Werkzeuge entwickelt wurden, und das vorgestellte Modell die gesamte Entwicklung verteilter multimedialer Anwendungen unterstützt, ist dieses große Gebiet noch lange nicht erschöpfend behandelt. Eine Erweiterung der Managementschnittstellen und die Realisierung von komplexen Werkzeugen sind die vordringlichsten Aufgaben. Damit entsteht ein mächtiges Entwicklungswerkzeug für Multimediaanwendungen. Funktionsorientierte Bausteine zur Integration kontinuierlicher Medien in verteilte Anwendungen Eine weitere Aufgabe ist die genauere Untersuchung der Nebenbedingungen, die zur Unterscheidung der Funktionen der Typen f 1 bis f 5 führten. Aus diesen Untersuchungen sowie aus den Ergebnissen der Ticker- und Schrittgeber-Realisierung lassen sich dann genauer spezifizierte Anforderungen an die Betriebs- oder Kommunikations-Systeme ableiten.
This paper describes the development of a typesetting program for music in the lazy functional programming language Clean. The system transforms a description of the music to be typeset in a dvi-file just like TEX does with mathematical formulae. The implementation makes heavy use of higher order functions. It has been implemented in just a few weeks and is able to typeset quite impressive examples. The system is easy to maintain and can be extended to typeset arbitrary complicated musical constructs. The paper can be considered as a status report of the implementation as well as a reference manual for the resulting system.
Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...
We address to the problem to factor a large composite number by lattice reduction algorithms. Schnorr has shown that under a reasonable number theoretic assumptions this problem can be reduced to a simultaneous diophantine approximation problem. The latter in turn can be solved by finding sufficiently many l_1--short vectors in a suitably defined lattice. Using lattice basis reduction algorithms Schnorr and Euchner applied Schnorrs reduction technique to 40--bit long integers. Their implementation needed several hours to compute a 5% fraction of the solution, i.e., 6 out of 125 congruences which are necessary to factorize the composite. In this report we describe a more efficient implementation using stronger lattice basis reduction techniques incorporating ideas of Schnorr, Hoerner and Ritter. For 60--bit long integers our algorithm yields a complete factorization in less than 3 hours.
We introduce the relationship between incremental cryptography and memory checkers. We present an incremental message authentication scheme based on the XOR MACs which supports insertion, deletion and other single block operations. Our scheme takes only a constant number of pseudorandom function evaluations for each update step and produces smaller authentication codes than the tree scheme presented in [BGG95]. Furthermore, it is secure against message substitution attacks, where the adversary is allowed to tamper messages before update steps, making it applicable to virus protection. From this scheme we derive memory checkers for data structures based on lists. Conversely, we use a lower bound for memory checkers to show that so-called message substitution detecting schemes produce signatures or authentication codes with size proportional to the message length.
We show lower bounds for the signature size of incremental schemes which are secure against substitution attacks and support single block replacement. We prove that for documents of n blocks such schemes produce signatures of \Omega(n^(1/(2+c))) bits for any constant c>0. For schemes accessing only a single block resp. a constant number of blocks for each replacement this bound can be raised to \Omega(n) resp. \Omega(sqrt(n)). Additionally, we show that our technique yields a new lower bound for memory checkers.
A memory checker for a data structure provides a method to check that the output of the data structure operations is consistent with the input even if the data is stored on some insecure medium. In [8] we present a general solution for all data structures that are based on insert(i,v) and delete(j) commands. In particular this includes stacks, queues, deques (double-ended queues) and lists. Here, we describe more time and space efficient solutions for stacks, queues and deques. Each algorithm takes only a single function evaluation of a pseudorandomlike function like DES or a collision-free hash function like MD5 or SHA for each push/pop resp. enqueue/dequeue command making our methods applicable to smart cards.
It is well known that first order uni cation is decidable, whereas second order and higher order unification is undecidable. Bounded second order unification (BSOU) is second order unification under the restriction that only a bounded number of holes in the instantiating terms for second order variables is permitted, however, the size of the instantiation is not restricted. In this paper, a decision algorithm for bounded second order unification is described. This is the fist non-trivial decidability result for second order unification, where the (finite) signature is not restricted and there are no restrictions on the occurrences of variables. We show that the monadic second order unification (MSOU), a specialization of BSOU is in sum p s. Since MSOU is related to word unification, this is compares favourably to the best known upper bound NEXPTIME (and also to the announced upper bound PSPACE) for word unification. This supports the claim that bounded second order unification is easier than context unification, whose decidability is currently an open question.
This paper describes context analysis, an extension to strictness analysis for lazy functional languages. In particular it extends Wadler's four point domain and permits in nitely many abstract values. A calculus is presented based on abstract reduction which given the abstract values for the result automatically finds the abstract values for the arguments. The results of the analysis are useful for veri fication purposes and can also be used in compilers which require strictness information.
The extraction of strictness information marks an indispensable element of an efficient compilation of lazy functional languages like Haskell. Based on the method of abstract reduction we have developed an e cient strictness analyser for a core language of Haskell. It is completely written in Haskell and compares favourably with known implementations. The implementation is based on the G#-machine, which is an extension of the G-machine that has been adapted to the needs of abstract reduction.
Syntactic coindexing restrictions are by now known to be of central importance to practical anaphor resolution approaches. Since, in particular due to structural ambiguity, the assumption of the availability of a unique syntactic reading proves to be unrealistic, robust anaphor resolution relies on techniques to overcome this deficiency. In this paper, two approaches are presented which generalize the verification of coindexing constraints to de cient descriptions. At first, a partly heuristic method is described, which has been implemented. Secondly, a provable complete method is specified. It provides the means to exploit the results of anaphor resolution for a further structural disambiguation. By rendering possible a parallel processing model, this method exhibits, in a general sense, a higher degree of robustness. As a practically optimal solution, a combination of the two approaches is suggested.
The paper focuses on the division of the sensor field into subsets of sensor events and proposes the linear transformation with the smallest achievable error for reproduction: the transform coding approach using the principal component analysis (PCA). For the implementation of the PCA, this paper introduces a new symmetrical, lateral inhibited neural network model, proposes an objective function for it and deduces the corresponding learning rules. The necessary conditions for the learning rate and the inhibition parameter for balancing the crosscorrelations vs. the autocorrelations are computed. The simulation reveals that an increasing inhibition can speed up the convergence process in the beginning slightly. In the remaining paper, the application of the network in picture encoding is discussed. Here, the use of non-completely connected networks for the self-organized formation of templates in cellular neural networks is shown. It turns out that the self-organizing Kohonen map is just the non-linear, first order approximation of a general self-organizing scheme. Hereby, the classical transform picture coding is changed to a parallel, local model of linear transformation by locally changing sets of self-organized eigenvector projections with overlapping input receptive fields. This approach favors an effective, cheap implementation of sensor encoding directly on the sensor chip. Keywords: Transform coding, Principal component analysis, Lateral inhibited network, Cellular neural network, Kohonen map, Self-organized eigenvector jets.
This paper describes the use of a radial basis function (RBF) neural network. It approximates the process parameters for the extrusion of a rubber profile used in tyre production. After introducing the problem, we describe the RBF net algorithm and the modeling of the industrial problem. The algorithm shows good results even using only a few training samples. It turns out that the „curse of dimensions“ plays an important role in the model. The paper concludes by a discussion of possible systematic error influences and improvements.
Das Thema dieser Arbeit ist die Dienstvermittlung in offenen verteilten Systemen und die Rolle, die ein Typsystem dabei einnimmt. Ein Typsystem besteht aus einer Typbeschreibungssprache und der Definition einer Typkonformität. Die Typbeschreibungssprache erlaubt die Spezifiation von Typen, wohingegen mit der Typkonformität während eines Vermittlungsvorgangs überprüft wird, ob Angebot und Nachfrage zusammenpassen. In dieser Arbeit wurde zunächst nachgewiesen, daß es sinnvoll ist, bei einem Typ zwischen seiner Intension und seiner Extension zu unterscheiden. Die Intension eines Typs ist die Gesamtheit aller Beschreibungen, die auf diesen zutreffen. Die Extension eines Typs repräsentiert dagegen eine konkrete Beschreibung (d.h. Spezifikation eines Dienstangebots). Eine Interpretation ordnet jeder Extension eine Intension zu. Um in einem offenen verteilten System Dienste vermitteln zu können, müssen sich Dienstnutzer und {anbieter auf die Extensionen aller Typen einigen. Einem Typ kommt hierdurch die Rolle eine Standards zu, der allen beteiligten Parteien a priori bekannt sein muß. Daraus resultiert eine injektive Interpretation, die jeder Intension genau eine Extension zuordnet. Die eindeutig bestimmte Extension einer Intension fungiert als systemweiter Standard. Ein Typ als Standard steht im Widerspruch zu der Vielfalt und Dynamik eines offenen Dienstmarktes. Der Standardisierungsprozeß von Extensionen, der einem Vermittlungsvorgang vorausgehen muß, hemmt gerade die Dynamik des Systems. Die Konsequenz daraus ist, daß neben den Diensten auch die Diensttypen Gegenstand der Vermittlung sein müssen. Diese Schlußfolgerung ist bisher noch nicht formuliert worden. Es wäre somit wünscheswert, nicht{injektive Interpretationen zuzulassen, so daß eine Intension mehrere Extensionen besitzen kann, die unterschiedliche Sichten der Dienstnutzer und {anbieter repräsentieren. Die Analyse einiger bestehender Typsysteme zeigte, daß mit diesen eine nicht-injektive Interpretation nicht realisierbar ist. Im Hauptteil dieser Arbeit wurden zwei neue Typsysteme vorgestellt, die diese Eigenschaft unterstützen. Das deklarative Typsystem erweitert die Schnittstellenbeschreibungssprache eines syntaktischen Typsystems, indem semantische Spezifiationen zugelassen werden. Die deklarative Semantik dient dabei als Grundlage für die Beschreibung der Semantik einer Typspezifikation. Die Extension entspricht einem definiten Programm bestehend aus einer endlichen Menge von Horn-Klauseln. Die Intension eines Typs korrespondiert mit dem kleinsten Herbrand-Modell des definiten Programms, welches die semantische Spezifikation des Typs darstellt. Die Forderung nach der Möglichkeit nicht{injektiver Interpretationen ergibt sich aus den Eigenschaften der deklarativen Semantik, wonach verschiedene definite Programme ein identisches kleinstes Herbrand-Modell besitzen können. Das zweite in dieser Arbeit vorgestellte Typsystem entspringt einem wissensbasierten Ansatz. Grundlage bildet eine Wissensrepräsentationstechnik, die anwenderbezogene semantische Spezifikationen erlaubt. Ein Konzeptgraph als wissensbasierte Typspezifikation vereinigt in sich unterschiedliche Beschreibungen eines Typs. Ein Konzeptgraph, der selbst eine Extension darstellt, repräsentiert somit die Vereinigung mehrerer Extensionen eines Typs. Die Intension ist jedoch durch einen Konzeptgraph nicht eindeutig bestimmt. Dieser stellt lediglich eine Approximation dar. Hier liegt ein fundamentaler Unterschied in den beiden Typsystemen. Während eine Extension im deklarativen Typsystem auch immer eindeutig eine Intension charakterisiert, ist dies bei dem wissensbasierten Typsystem nicht der Fall. Die Konsequenz daraus ist, daß dieser Umstand bei einem Vermittlungsvorgang berücksichtigt werden muß. Ein wissensbasierter Vermittler muß über ein spezielles Vermittlungsprotokoll die Verfeinerung einer wissensbasierten Typspezifikation erlauben, die zu einer besseren Approximation der Intension führt. Das deklarative Typsystem besitzt aufgrund der Unentscheidbarkeit der deklarativen Typkonformität keine praktische Relevanz. Es zeigt jedoch, wie mit Hilfe der deklarativen Semantik der Open World Assumption genüge geleistet werden kann. Im Vergleich dazu kann das wissensbasierte Typsystem als "Fuzzyfizierung" des deklarativen Typsystems angesehen werden. Die wissensbasierte Typbeschreibungssprache ermöglicht im Sinne der Fuzzy Logik unscharfe Spezifikationen, die im Laufe der Zeit verfeinert werden. Ein Vorteil des wissensbasierten Ansatzes ist die Möglichkeit von anwenderbezogenen Typspezifikationen. Ein anderer Vorteil besteht darin, daß eine wissensbasierte Typbeschreibungssprache eine Meta-Sprache repräsentiert, in der Spezifikationen aus anderen Domänen dargestellt werden können. Ungeachtet dieser Vorteile bleibt jedoch der Beweis offen, daß die wissensbasierte Dienstvermittlung tatsächlich eine geeignete Methodik für die Vermittlung von Typen darstellt.
Automatic termination proofs of functional programming languages are an often challenged problem Most work in this area is done on strict languages Orderings for arguments of recursive calls are generated In lazily evaluated languages arguments for functions are not necessarily evaluated to a normal form It is not a trivial task to de ne orderings on expressions that are not in normal form or that do not even have a normal form We propose a method based on an abstract reduction process that reduces up to the point when su cient ordering relations can be found The proposed method is able to nd termination proofs for lazily evaluated programs that involve non terminating subexpressions Analysis is performed on a higher order polymorphic typed language and termi nation of higher order functions can be proved too The calculus can be used to derive information on a wide range on di erent notions of termination.
Korrektur zu: C.P. Schnorr: Security of 2t-Root Identification and Signatures, Proceedings CRYPTO'96, Springer LNCS 1109, (1996), pp. 143-156 page 148, section 3, line 5 of the proof of Theorem 3. Die Korrektur wurde präsentiert als: "Factoring N via proper 2 t-Roots of 1 mod N" at Eurocrypt '97 rump session.
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
Given x small epsilon, Greek Rn an integer relation for x is a non-trivial vector m small epsilon, Greek Zn with inner product <m,x> = 0. In this paper we prove the following: Unless every NP language is recognizable in deterministic quasi-polynomial time, i.e., in time O(npoly(log n)), the ℓinfinity-shortest integer relation for a given vector x small epsilon, Greek Qn cannot be approximated in polynomial time within a factor of 2log0.5 − small gamma, Greekn, where small gamma, Greek is an arbitrarily small positive constant. This result is quasi-complementary to positive results derived from lattice basis reduction. A variant of the well-known L3-algorithm approximates for a vector x small epsilon, Greek Qn the ℓ2-shortest integer relation within a factor of 2n/2 in polynomial time. Our proof relies on recent advances in the theory of probabilistically checkable proofs, in particular on a reduction from 2-prover 1-round interactive proof-systems. The same inapproximability result is valid for finding the ℓinfinity-shortest integer solution for a homogeneous linear system of equations over Q.
We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
A partial rehabilitation of side-effecting I/O : non-determinism in non-strict functional languages
(1996)
We investigate the extension of non-strict functional languages like Haskell or Clean by a non-deterministic interaction with the external world. Using call-by-need and a natural semantics which describes the reduction of graphs, this can be done such that the Church-Rosser Theorems 1 and 2 hold. Our operational semantics is a base to recognise which particular equivalencies are preserved by program transformations. The amount of sequentialisation may be smaller than that enforced by other approaches and the programming style is closer to the common one of side-effecting programming. However, not all program transformations used by an optimising compiler for Haskell remain correct in all contexts. Our result can be interpreted as a possibility to extend current I/O-mechanism by non-deterministic deterministic memoryless function calls. For example, this permits a call to a random number generator. Adding memoryless function calls to monadic I/O is possible and has a potential to extend the Haskell I/O-system.
An anaphor resolution algorithm is presented which relies on a combination of strategies for narrowing down and selecting from antecedent sets for re exive pronouns, nonre exive pronouns, and common nouns. The work focuses on syntactic restrictions which are derived from Chomsky's Binding Theory. It is discussed how these constraints can be incorporated adequately in an anaphor resolution algorithm. Moreover, by showing that pragmatic inferences may be necessary, the limits of syntactic restrictions are elucidated.
We present a framework for the self-organized formation of high level learning by a statistical preprocessing of features. The paper focuses first on the formation of the features in the context of layers of feature processing units as a kind of resource-restricted associative multiresolution learning We clame that such an architecture must reach maturity by basic statistical proportions, optimizing the information processing capabilities of each layer. The final symbolic output is learned by pure association of features of different levels and kind of sensorial input. Finally, we also show that common error-correction learning for motor skills can be accomplished also by non-specific associative learning. Keywords: feedforward network layers, maximal information gain, restricted Hebbian learning, cellular neural nets, evolutionary associative learning
After a short introduction into traditional image transform coding, multirate systems and multiscale signal coding the paper focuses on the subject of image encoding by a neural network. Taking also noise into account a network model is proposed which not only learns the optimal localized basis functions for the transform but also learns to implement a whitening filter by multi-resolution encoding. A simulation showing the multi-resolution capabilitys concludes the contribution.
We call a vector x/spl isin/R/sup n/ highly regular if it satisfies =0 for some short, non-zero integer vector m where <...> is the inner product. We present an algorithm which given x/spl isin/R/sup n/ and /spl alpha//spl isin/N finds a highly regular nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no short relation m~ of length less than /spl alpha//2 exists for points x~ within half the x'-distance from x. The integer relation m for x' is for random x up to an average factor 2/sup /spl alpha//2/ a shortest integer relation for x'. Our algorithm uses, for arbitrary real input x, at most O(n/sup 4/(n+log A)) many arithmetical operations on real numbers. If a is rational the algorithm operates on integers having at most O(n/sup 5/+n/sup 3/(log /spl alpha/)/sup 2/+log(/spl par/qx/spl par//sup 2/)) many bits where q is the common denominator for x.
We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lattice basis b1,b2,...,bn is given such that the vector of reduced Gram-Schmidt coefficients ({µi,j} 1<= j< i<= n) is uniformly distributed in [0,1)n(n-1)/2, then the pruned enumeration finds with positive probability a shortest lattice vector. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking Damgard's hash function.
Die Anfänge der Gittertheorie reichen in das letzte Jahrhundert, wobei die wohl bekanntesten Ergebnisse auf Gauß, Hermite und Minkowski zurückgehen. Die Arbeiten sind jedoch zumeist in der Schreibweise der quadratischen Formen verfaßt, erst in den letzten Jahrzehnten hat sich die von uns verwendete Gitterschreibweise durchgesetzt. Diese ist zum einen geometrisch anschaulicher, zum anderen wurden in den letzten Jahren für diese Schreibweise effiziente Algorithmen entwickelt, so daß Probleme der Gittertheorie mittels Computer gelöst werden können. Ein wichtiges Problem ist, in einem Gitter einen kürzesten nicht verschwindenden Vektor zu bestimmen. Den Grundstein für diese algorithmische Entwicklung legten A.K. Lenstra, H.W. Lenstra Jr. und L. Lovasz mit ihrer Arbeit. In dieser führten sie einen Reduktionsbegriff ein, der durch einen Polynomialzeitalgorithmus erreicht werden kann. Ein weiterer Reduktionsbegriff, die Blockreduktion, geht auf Schnorr zurück. Euchner hat im Rahmen seiner Diplomarbeit effiziente Algorithmen für diese beiden Reduktionsbegriffe auf Workstations implementiert und auch in Dimensionen > 100 erfolgreich getestet. Die Verbesserungen von Schnittechniken des in der Blockreduktion verwendeten Aufzählungsverfahrens und die Einführung einer geschnittenen Aufzählung über die gesamte Gitterbasis hat Hörner in seiner Diplomarbeit beschrieben. Ziel der folgenden Arbeit war es nun, diese bereits auf sequentiellen Computern implementierten Algorithmen zu modifizieren, um auf parallelen Rechnern, speziell Vektorrechnern, einen möglichst hohen Geschwindigkeitsgewinn zu erzielen. Wie in den seriellen Algorithmen werden die Basisvektoren stets in exakter Darstellung mitgeführt, so daß das Endergebnis einer Berechnung nicht durch Rundungsfehler verfälscht wird.