Informatik
Refine
Year of publication
Document Type
- Preprint (748)
- Article (401)
- Working Paper (119)
- Doctoral Thesis (93)
- Diploma Thesis (46)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (36)
- 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 (1607)
Is part of the Bibliography
- no (1607)
Keywords
Institute
- Informatik (1607)
- 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)
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.
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.
We consider unification of terms under the equational theory of two-sided distributivity D with the axioms x*(y+z) = x*y + x*z and (x+y)*z = x*z + y*z. The main result of this paper is that Dunification is decidable by giving a non-deterministic transformation algorithm. The generated unification are: an AC1-problem with linear constant restrictions and a second-order unification problem that can be transformed into a word-unification problem that can be decided using Makanin's algorithm. This solves an open problem in the field of unification. Furthermore it is shown that the word-problem can be decided in polynomial time, hence D-matching is NP-complete.
We consider the problem of unifying a set of equations between second-order terms. Terms are constructed from function symbols, constant symbols and variables, and furthermore using monadic second-order variables that may stand for a term with one hole, and parametric terms. We consider stratified systems, where for every first-order and second-order variable, the string of second-order variables on the path from the root of a term to every occurrence of this variable is always the same. It is shown that unification of stratified second-order terms is decidable by describing a nondeterministic decision algorithm that eventually uses Makanin's algorithm for deciding the unifiability of word equations. As a generalization, we show that the method can be used as a unification procedure for non-stratified second-order systems, and describe conditions for termination in the general case.
Funktionale Programmiersprachen weisen viele Eigenschaften auf, die zur modernen Softwareentwicklung benotigt werden: Zuverlässigkeit, Modularisierung, Wiederverwendbarkeit und Verifizierbarkeit. Als schwer vereinbar mit diesen Sprachen stellte sich die Einbettung von Seiteneffekten in diese Sprachen heraus. Nach einigen mehr oder weniger gescheiterten Ansätzen hat sich mittlerweile fur die nichtstrikte funktionale Sprache Haskell der monadische Ansatz durchgesetzt, bei dem die Seiteneffekte geschickt verpackt werden, so dass zumindest IO-behaftete Teile eines Haskell-Programms dem klassischen imperativen Programmierstil ähneln. S. Peyton Jones bringt dieses in [Pey01, Seite 3] auf den Punkt, indem er schreibt "...Haskell is the world's finest imperative programming language." Dies ist einerseits vorteilhaft, denn die klassischen Programmiertechniken können angewendet werden, andererseits bedeutet dies auch eine Rückkehr zu altbekannten Problemen in diesen Sprachen: Der Programmcode wird unverständlicher, die Wiederverwendbarkeit von Code verschlechtert sich, Änderungen im Programm sind aufwendig. Zudem erscheint die monadische Programmierung teilweise umständlich. Deshalb wurde im Zuge der Entwicklung in fast jede Implementierung von Haskell ein Konstrukt eingebaut, dass von monadischem IO zu direktem IO führt. Da dieses nicht mit dem bisherigen Ansatz vereinbar schien, wird es als "unsafe" bezeichnet, die entsprechende Funktion heißt "unsafePerformIO". Zahlreiche Anwendungen benutzten diese Funktion, teilweise scheint die Verwendung zumindest aus Effizienzgründen unabdingbar. Allerdings ist die Frage, wann dieses verwendet werden darf, d.h. so angewendet wird, dass es nicht "unsicher" ist, nur unzureichend geklärt. Das Zitat in Abbildung 1.1 gibt wenig Aufschluss über die korrekte Anwendung, zumal immer wieder Diskussionen entstehen, ob die Verwendung von unsafePerformIO in diesem oder jenem Spezialfall korrekt ist.
The wide-area deployment of WiFi hot spots challenges IP access providers. While new profit models are sought after by them, profitability as well as logistics for large-scale deployment of 802.11 wireless technology are still to be proven. Expenditure for hardware, locations, maintenance, connectivity, marketing, billing and customer care must be considered. Even for large carriers with infrastructure, the deployment of a large-scale WiFi infrastructure may be risky. This paper proposes a multi-level scheme for hot spot distribution and customer acquisition that reduces financial risk, cost of marketing and cost of maintenance for the large-scale deployment of WiFi hot spots.
Entwurf und prototypische Realisierung einer Architektur zur flexiblen Verschlüsselung von XML-Daten
(2001)
Im Rahmen dieser Arbeit ist auf Basis einer sorgfältigen Prüfung existierender Literatur zu kryptografischen Verfahren und sowohl einer Analyse bestehender Ansätze zur Verschlüsselung von XML-Dokumenten, als auch unter Nutzung bestehender Standards für XML-Technologien, eine Architektur zur flexiblen Verschlüsselung von XML-Daten erstellt worden. Ausgehend von Einsatz-Szenarien wurden dazu Anforderungen an das gewünschte System definiert. Anhand dieser Anforderungen wurde systematisch eine vollständige Spezifikation zur Verschlüsselung von XML-Daten hergeleitet. Weiterhin ist eine erweiterbare und generische Architektur zur Verarbeitung von XML-Daten spezifiziert worden. Auf dieser aufbauend, wurde eine Architektur für die flexible Ver- und Entschlüsselung von XML-Daten erstellt. Diese Architekturen und ihre Komponenten sind generisch, wobei für die prototypische Realisierung exemplarisch eine konkrete Auswahl dieser Komponenten implementiert wurde. Für die Verschlüsselung wurde dazu auf die zuvor erstellte Spezifikation zurückgegriffen und deren relevante Teile implementiert. Anschliessend wurden Experimente durchgeführt, die einen Eindruck von der Leistungsfähigkeit der Architektur gegeben haben. Insgesamt haben sich die Erwartungen an die Architektur mehr als erfüllt. Stehen Transformationen als verwendbare Klassen bereit, die auf dem DOM operieren, so ist es leicht möglich, diese in das DPF einzubetten, wie z.B. beim Verschlüsselungs-Prozessor geschehen. Damit ist eine sehr gute Erweiterbarkeit gegeben. Da die Arbeitsweise eines Transformations-Prozessors sowohl direkt durch übergebene Argumente aus dem DPS als auch durch die Verwendung von Annotationen gesteuert werden kann, kann die Verarbeitung von Dokumenten sehr flexibel und auch feingranular erfolgen. Die Möglichkeit, Annotationen aus mehreren DAS-Dokumenten zu aggregieren, erlaubt eine verteilte Pflege dieser Dokumente. Mit der Möglichkeit, mehrere Prozessoren direkt nacheinander eine Eingabe bearbeiten zu lassen, wird die Flexibilität nochmals gesteigert. Denn wenn die Prozessoren als Komponenten zur Verfügung stehen, können diese stets aufs Neue kombiniert werden. Vor allem der Ansatz, dass alle zur Verarbeitung und Steuerung relevanten Daten in Form deklarativer Beschreibungen erfolgen, die den Bedürfnissen jedes Prozessors angepasst sind, macht das System zu einem mächtigen Instrument. Zudem werden dadurch keine tiefergehenden Programmierkenntnisse benötigt. So entfällt auch die Notwendigkeit, Änderungen des gewünschten Transformations-Ergebnisses durch Änderungen im Quelltext des erzeugenden Programms vorzunehmen. Dadurch sind insgesamt den Möglichkeiten zur Verarbeitung von XML-Dokumenten kaum Grenzen gesetzt. Notwendige Anpassungen bleiben zumeist auf eine oder wenige Komponenten beschränkt, was Änderungen leichter ermöglicht. Dabei hat sich wieder einmal der flexible und trotzdem mächtige Ansatz der Kette von Werkzeugen (Chain of Tools) bewährt. Auch die Spezifikation zur Verschlüsselung von XML-Daten konnte alle Erwartungen erfüllen. Alle eingangs gestellten Anforderungen sind damit ausnahmslos darstellbar. Insbesondere betrifft dies die partielle und feingranulare Verschlüsselung von XML-Daten, sowie die hierarchische und damit einhergehende Super-Verschlüsselung. Rückblickend kann gesagt werden, dass das wissenschaftliche Fundament in Form von kryptografischen Grundlagen zwar sehr gut ist, aber die darauf aufbauenden höherwertigen Dienste und Architekturen aus wissenschaftlicher Sicht bisher kaum Beachtung gefunden haben. So wird zwar die Verschlüsselung von ganzen Daten-Objekten zwischen zwei Empfängern gut beherrscht, aber eine feingranulare Verschlüsselung, bei der Daten an grosse dynamische Empfängergruppen in offenen Systemen vertraulich übermittelt werden, hat bisher keine Beachtung gefunden. In der vorliegenden Arbeit werden diese Probleme adressiert, wobei aber nicht für alle eine abschliessende Lösung präsentiert werden konnte, da dies den Rahmen der Arbeit gesprengt hätte. Vielleicht ist es gerade die fehlende wissenschaftliche Durchdringung, die es so schwierig macht, geeignete Standards für die Verschlüsselung von XML-Dokumenten zu etablieren. Denn wenn man betrachtet, wie lange schon beim W3C über die Verschlüsselung diskutiert und daran gearbeitet wird, so kann es einen nur verwundern, dass nicht greifbarere Ergebnisse vorliegen. Ende Juli, also kurz vor Abschluss der vorliegenden Arbeit, ist bei Recherchen noch ein wissenschaftlich fundierteres Papier aufgetaucht, das auf einer Konferenz im Juni dieses Jahres vorgestellt wurde. Es beschreibt eine Document Security Language (DSL), die auf XSLT beruht und eine Architektur zur Verschlüsselung von XML-Dokumenten [85]. Da die Nähe zu dieser Arbeit gross ist, soll sie hier noch kurz vergleichend betrachtet werden. Die dort beschriebene Architektur und die Sprache bietet auch die Verschlüsselung auf feingranularer Ebene. Aber sie ist nicht erweiterbar und kennt auch kein generisches Meta-Daten-Konzept, so dass sie hinter den Ergebnissen der vorliegenden Arbeit deutlich zurückfällt. Zudem beruht sie auf der vorne schon im Zusammenhang mit der Verwendung von XSLT kritisierten Arbeit in [48]. Sie trägt dazu im Bereich der Verschlüsselung nicht viel Neues bei. Allerdings weist sie einige interessante Ansätze im Bereich der Infrastrukturen auf [85, Abschnitt 3.2]. Um diese könnte die hier vorgestellte Architektur der Verschlüsselungs-Prozessoren ergänzt werden, denn dieses Gebiet wurde in der Arbeit ausgespart.