Refine
Year of publication
- 2003 (19) (remove)
Document Type
- Working Paper (5)
- Conference Proceeding (3)
- diplomthesis (3)
- Article (2)
- Diploma Thesis (2)
- Part of a Book (1)
- Doctoral Thesis (1)
- Preprint (1)
- Review (1)
Has Fulltext
- yes (19)
Is part of the Bibliography
- no (19)
Keywords
- Kongress (2)
- Beschreibungskomplexität (1)
- Collaborative Filtering (1)
- Computerlinguistik (1)
- Content-Based Filtering (1)
- Dreidimensionale Computergraphik (1)
- Entwurfsmuster (1)
- Frankfurt <Main, 2003> (1)
- Infomediary (1)
- Informatik (1)
Institute
- Informatik (19) (remove)
Suche im Semantic Web : Erweiterung des VRP um eine intuitive und RQL-basierte Anfrageschnittstelle
(2003)
Datenflut im World Wide Web - ein Problem jedes Internetbenutzers. Klassische Internetsuchmaschinen sind überfordert und liefern immer seltener brauchbare Resultate. Das Semantic Web verspricht Hoffnung - maßgeblich basierend auf RDF. Das Licht der Öffentlichkeit erblickt das Semantic Web vermutlich zunächst in spezialisierten Informationsportalen, so genannten Infomediaries. Besucher von Informationsportalen benötigen eine Abfragesprache, welche ebenso einfach wie eine gewöhnliche Internetsuchmaschine anzuwenden ist. Eine derartige Abfragesprache existiert für RDF zur Zeit nicht. Diese Arbeit stellt eine neuartige Abfragesprache vor, welche dieser Anforderung genügt: eRQL. Bestandteil dieser Arbeit ist der mittels Java implementierte eRQL-Prozessor eRqlEngine, welcher unter http://www.wleklinski.de/rdf/ und unter http://www.dbis.informatik.uni-frankfurt.de/~tolle/RDF/eRQL/ bezogen werden kann.
Coreference-Based Summarization and Question Answering: a Case for High Precision Anaphor Resolution
(2003)
Approaches to Text Summarization and Question Answering are known to benefit from the availability of coreference information. Based on an analysis of its contributions, a more detailed look at coreference processing for these applications will be proposed: it should be considered as a task of anaphor resolution rather than coreference resolution. It will be further argued that high precision approaches to anaphor resolution optimally match the specific requirements. Three such approaches will be described and empirically evaluated, and the implications for Text Summarization and Question Answering will be discussed.
We enhance the security of Schnorr blind signatures against the novel one-more-forgery of Schnorr [Sc01] andWagner [W02] which is possible even if the discrete logarithm is hard to compute. We show two limitations of this attack. Firstly, replacing the group G by the s-fold direct product G exp(×s) increases the work of the attack, for a given number of signer interactions, to the s-power while increasing the work of the blind signature protocol merely by a factor s. Secondly, we bound the number of additional signatures per signer interaction that can be forged effectively. That fraction of the additional forged signatures can be made arbitrarily small.
We present a novel practical algorithm that given a lattice basis b1, ..., bn finds in O(n exp 2 *(k/6) exp (k/4)) average time a shorter vector than b1 provided that b1 is (k/6) exp (n/(2k)) times longer than the length of the shortest, nonzero lattice vector. We assume that the given basis b1, ..., bn has an orthogonal basis that is typical for worst case lattice bases. The new reduction method samples short lattice vectors in high dimensional sublattices, it advances in sporadic big jumps. It decreases the approximation factor achievable in a given time by known methods to less than its fourth-th root. We further speed up the new method by the simple and the general birthday method. n2
This paper proposes a non-standard way to combine lazy functional languages with I/O. In order to demonstrate the usefulness of the approach, a tiny lazy functional core language FUNDIO , which is also a call-by-need lambda calculus, is investigated. The syntax of FUNDIO has case, letrec, constructors and an IO-interface: its operational semantics is described by small-step reductions. A contextual approximation and equivalence depending on the input-output behavior of normal order reduction sequences is defined and a context lemma is proved. This enables to study a semantics of FUNDIO and its semantic properties. The paper demonstrates that the technique of complete reduction diagrams enables to show a considerable set of program transformations to be correct. Several optimizations of evaluation are given, including strictness optimizations and an abstract machine, and shown to be correct w.r.t. contextual equivalence. Correctness of strictness optimizations also justifies correctness of parallel evaluation. Thus this calculus has a potential to integrate non-strict functional programming with a non-deterministic approach to input-output and also to provide a useful semantics for this combination. It is argued that monadic IO and unsafePerformIO can be combined in Haskell, and that the result is reliable, if all reductions and transformations are correct w.r.t. to the FUNDIO-semantics. Of course, we do not address the typing problems the are involved in the usage of Haskell s unsafePerformIO. The semantics can also be used as a novel semantics for strict functional languages with IO, where the sequence of IOs is not fixed.
In this paper we demonstrate how to relate the semantics given by the nondeterministic call-by-need calculus FUNDIO [SS03] to Haskell. After introducing new correct program transformations for FUNDIO, we translate the core language used in the Glasgow Haskell Compiler into the FUNDIO language, where the IO construct of FUNDIO corresponds to direct-call IO-actions in Haskell. We sketch the investigations of [Sab03b] where a lot of program transformations performed by the compiler have been shown to be correct w.r.t. the FUNDIO semantics. This enabled us to achieve a FUNDIO-compatible Haskell-compiler, by turning o not yet investigated transformations and the small set of incompatible transformations. With this compiler, Haskell programs which use the extension unsafePerformIO in arbitrary contexts, can be compiled in a "safe" manner.
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.
We investigate a restricted one-way cellular automaton (OCA) model where the number of cells is bounded by a constant number k, so-called kC-OCAs. In contrast to the general model, the generative capacity of the restricted model is reduced to the set of regular languages. A kC-OCA can be algorithmically converted to a deterministic finite automaton (DFA). The blow-up in the number of states is bounded by a polynomial of degree k. We can exhibit a family of unary languages which shows that this upper bound is tight in order of magnitude. We then study upper and lower bounds for the trade-off when converting DFAs to kC-OCAs. We show that there are regular languages where the use of kC-OCAs cannot reduce the number of states when compared to DFAs. We then investigate trade-offs between kC-OCAs with different numbers of cells and finally treat the problem of minimizing a given kC-OCA.
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.