| Bibliography | Hantschel, Ralf: Über das Wachstum von Boyer-Moore-Automaten.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 2557 (2007).
150 pages, german.
|
|---|
| CR-Schema | F.1.1 (Models of Computation)
F.1.2 (Modes of Computation)
G.1.6 (Numerical Analysis Optimization)
I.2.8 (Problem Solving, Control Methods, and Search)
I.5.4 (Pattern Recognition Applications)
K.5.2 (Legal Aspects of Computing Governmental Issues)
|
|---|
| Keywords | Boyer-Moore-Automat; Evolution; Evolutionäre Algorithmen; Genetischer Algorithmus; vollständige Suche; Automaten |
|---|
| Abstract | In dieser Arbeit wird untersucht, in welchem Ausmaß Boyer-Moore-Automaten, abhängig vom zu suchenden Suchwort wachsen. Von manchen wird ein exponentielles Wachstum vermutet, andere behaupten dagegen, dass das Wachstum nur polynomiell ist. Es wird für einfache Fälle (kleines Alphabet, kurzes Suchwort) das Suchwort ermittelt, für welches die Anzahl der Zustände des zugehörigen Boyer-Moore-Automaten maximal wird. Bei einem zweielementigen Alphabet ist dies bis zur Suchwortlänge 30 möglich, bei einem dreielementigen Alphabet bis zur Suchwortlänge 19. Für längere Suchworte wird ein Genetischer Algorithmus entwickelt, der versucht die Suchworte zu finden, die sehr große Boyer-Moore-Automaten erzeugen.
|
|---|
Full text and
other links | PDF (3220394 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations |
|---|
| Contact | ralf_hantschel@gmx.de |
|---|
| Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Formal Concepts
|
|---|
| Entry date | May 18, 2007 |
|---|