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)
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.
The descriptional complexity of iterative arrays (lAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that lAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between lAs working in linear time and lAs working in real time. Furthermore, the descriptional complexity of lAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for lAs are undecidable and not semidecidable.
The Internet as the biggest human library ever assembled keeps on growing. Although all kinds of information carriers (e.g. audio/video/hybrid file formats) are available, text based documents dominate. It is estimated that about 80% of all information worldwide stored electronically exists in (or can be converted into) text form. More and more, all kinds of documents are generated by means of a text processing system and are therefore available electronically. Nowadays, many printed journals are also published online and may even discontinue to appear in print form tomorrow. This development has many convincing advantages: the documents are both available faster (cf. prepress services) and cheaper, they can be searched more easily, the physical storage only needs a fraction of the space previously necessary and the medium will not age. For most people, fast and easy access is the most interesting feature of the new age; computer-aided search for specific documents or Web pages becomes the basic tool for information-oriented work. But this tool has problems. The current keyword based search machines available on the Internet are not really appropriate for such a task; either there are (way) too many documents matching the specified keywords are presented or none at all. The problem lies in the fact that it is often very difficult to choose appropriate terms describing the desired topic in the first place. This contribution discusses the current state-of-the-art techniques in content-based searching (along with common visualization/browsing approaches) and proposes a particular adaptive solution for intuitive Internet document navigation, which not only enables the user to provide full texts instead of manually selected keywords (if available), but also allows him/her to explore the whole database.
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. In this paper, for the small, important example of inflammation modeling a network is constructed and different learning algorithms are proposed. It turned out that due to the nonlinear dynamics evolutionary approaches are necessary to fit the parameters for sparse, given data. Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence - ICTAI 2003
We investigate unary regular languages and compare deterministic finite automata (DFA’s), nondeterministic finite automata (NFA’s) and probabilistic finite automata (PFA’s) with respect to their size. Given a unary PFA with n states and an e-isolated cutpoint, we show that the minimal equivalent DFA has at most n exp 1/2e states in its cycle. This result is almost optimal, since for any alpha < 1 a family of PFA’s can be constructed such that every equivalent DFA has at least n exp alpha/2e states. Thus we show that for the model of probabilistic automata with a constant error bound, there is only a polynomial blowup for cyclic languages. Given a unary NFA with n states, we show that efficiently approximating the size of a minimal equivalent NFA within the factor sqrt(n)/ln n is impossible unless P = NP. This result even holds under the promise that the accepted language is cyclic. On the other hand we show that we can approximate a minimal NFA within the factor ln n, if we are given a cyclic unary n-state DFA.
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.
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.
Immer mehr Hersteller bringen kleine mobile Endgeräte (PDAs1) auf den Markt, die via WLAN2 (IEEE 802.11), Bluetooth oder UMTS3 drahtlos Kontakt mit der Außenwelt aufnehmen können. Dabei werden neben zunehmend höheren Übertragungsraten auch große Fortschritte in der Miniaturisierung erzielt. Viele PDAs besitzen bereits eingebaute Funknetzwerk-Karten, bei vielen läßt sich eine solche Karte einfach zusätzlich in das Gerät einstecken. Durch die steigende Rechenleistung der Geräte und die gleichzeitig steigenden Übertragungsraten der Funkverbindungen entstehen diverse neue Anwendungsmöglichkeiten, die allerdings noch wenig ausgenutzt werden. Es überwiegen die Standardaufgaben der PDAs, wie die Termin und die Adressenverwaltung. Ein eventuell vorhandener Zugang zu Netzwerken wird meist ebenfalls nur für Standardanwendungen verwendet, wie z.B. die Synchronisation von Daten mit einem Server, der Zugang zum World Wide Web oder zum Versenden von e-Mails. Der herkömmliche Zugang zu Netzwerken ist meist ortsgebunden. Im sogenannten Infrastruktur-Modus ist man auf eine Basisstation (Access-Point) angewiesen. Bewegt man sich in Bereichen, in denen kein solcher Access-Point zur Verfügung steht, kann eine Netzwerkverbindung nicht hergestellt werden. Die Mobilität des Benutzers ist auf die Funkreichweite seines Geräts zu dieser Basisstation beschränkt. Die Bezeichnung „mobil“ trifft also nur auf das Endgerät, nicht auf die Basisstation zu. Genutzt werden üblicherweise die gleichen Dienste wie in einem kabelgebundenem Netz, nämlich Server des Intra-, bzw. Internets. Die eigenständige Vernetzung mobiler Geräte untereinander, der sogenannte Ad-hoc-Modus, eröffnet neuartige Anwendungsgebiete. Ursprünglich dafür gedacht, zwei Stationen schnell und einfach über Funk miteinander zu verbinden, können durch eine Erweiterung beliebig viele Stationen zu einem spontanen und mobilen Netzwerk zusammengefaßt werden (mobiles Ad-hoc Netzwerk, MANET). Eine zentral verwaltete Infrastruktur entfällt dabei vollständig. Die Aufgaben des Routings muß jede einzelne der beteiligten Stationen übernehmen. Auf diese Weise erhöht sich die Funkreichweite aller beteiligten Stationen, da nicht ein zentraler Access-Point, sondern jeder beliebige Teilnehmer in Reichweite den Zugriff auf das Netzwerk ermöglicht. Es muß dabei allerdings davon ausgegangen werden, daß sich die Stationen in einem solchen Netz ständig bewegen, das Netz verlassen oder neu hinzukommen können. Somit verändert sich andauernd die Netzwerktopologie und ein kontinuierliches und selbstständiges Neuorganisieren des Netzes wird notwendig. Man spricht daher von selbstorganisierenden mobilen Netzen. Der Informationsfluß in Ad-hoc Netzen ist üblicherweise ein anderer als in Festnetzen. Es entsteht eine eher interessensbezogene Kommunikation, weniger eine, die auf dem Wissen von bekannten Endpunkten im Netzwerk basiert. In Ad-hoc Netzwerken können Endpunkte und Adressen aufgrund der sich permanent ändernden Nutzerzusammensetzung naturgemäß nicht bekannt sein. Stattdessen gibt jeder Nutzer Informationen über seine Interessen und seine Angebote im Netzwerk bekannt. Findet sich ein zu diesem Interessensprofil passendes Angebot, so kommt eine Verbindung zustande. Die Flexibilität der PDAs, ihre Mobilität und ihre ständig steigende Leistung lassen die Entwicklung von mobilen Ad-hoc-Anwendungen sinnvoll erscheinen. MANET Netzwerke sind in ihrer Auslegung flexibel und schnell, genau so, wie es die modernen PDAs sind. Es eröffnet sich durch durch beides eine große Zahl neuer und innovativer Anwendungsmöglichkeiten. Eine davon, das so genannte E-Learning, soll im Folgenden näher betrachtet werden. E-Learning ist ein Beispiel für eine Anwendung in Ad-hoc Netzen, die besonders geeignet erscheint, die Beweglichkeit ihrer Anwender in vielerlei Hinsicht zu unterstützen. Durch die Eigenschaft, geeignete Kollaborationspartner und Informationen schnell und gezielt im Netzwerk finden zu können, wird ein spontaner Wissensaustausch über die bisher bestehende Grenzen hinaus möglich. Es werden im Rahmen dieser Diplomarbeit Mechanismen behandelt, die dem Anwender die Nutzung von kollaborativen Anwendungen wie dem E-Learning ermöglichen und ihn bei dessen Nutzung unterstützen sollen.
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