idw – Informationsdienst Wissenschaft
Nachrichten, Termine, Experten
Nachrichten, Termine, Experten
Informatik: Uraltes Basiswerkzeug fuer die moderne mechanische Algebra neu "geschaerft"
Lexikographische Ordnungen und Stellensysteme mit ziffernabhaengigem Taktmass
Am Theorielehrstuhl der Erlanger Informatik (Prof. Dr. Klaus Leeb) der Universitaet Erlangen-Nuernberg wurde am 6.2.1998 durch Einfuehrung reeller bis infinitesimaler Laengen fuer die je einzelnen Buchstaben eine reichhaltige Klasse "lexikographischer" und Stellensystem-Ordnungen geschaffen. Dies kommt einem dringenden Beduerfnis der modernen mechanischen Algebra nach konkatenationsvertraeglichen Ordnungen nach. Waehrend fuer 4000 Jahre das Taktmass zum Ablesen von Zahlen und Woertern sehr eintoenig war, gestalten nun die Ziffern den Rhythmus ihrer Stellen selbst.
Uraltes Werkzeug der Mathematik und der Lexikologie
Eines der fundamentalen Werkzeuge der schriftkundigen Menschheit ist die lexikographische Anordnung. Stellensysteme zur Zahlendarstellung gibt es seit der Zeit der Sumerer, die lexikographische Ordnung von Woertern seit Alexandrias Lexikologie. Und wenn heute ein Mathematiker oder Algorithmiker keine natuerliche Ordnung fuer zu erledigende Einzelaufgaben erkennt, so arbeitet er lexikographisch, d.h. sinnfrei schematisch AB, AC, BC, ... . Man braucht nur mit dem Suchwort "lexicographic" ein x-beliebiges Algorithmikjournal zu durchforsten und bekommt mit schoener Regelmaessigkeit seine Treffer.
Schon die vor 3700 Jahren von Hammurapi gefoerderten Mathematiker waren imstande, in den Tabellen fuer Zinseszins und exponentielles Wachstum ihre sexagesimal entwickelten Zahlen groessenmaessig zu vergleichen. Seit jener Zeit war eine und dieselbe Laenge 1 fuer jedes Symbol das Taktmass fuer das Lesen entlang einer Zahl oder eines Worts. Zahlreiche wissenschaftliche Handbuecher - etwa das Handbook of Theoretical Computer Science, das Handbook of Combinatorics, das Handbook of Algorithms, of Statistics - kennen nur diese klassische lexikographische Ordnung festen Masses. Eine aus dem vorliegenden Anlass durchgefuehrte flaechendeckende elektronische und telephonische Recherche bestaetigte, dass auch von Spezialisten fuer angeordnete algebraische Systeme am state of the art nicht geruettelt wurde.
Im Zusammenhang mit mechanisierter universeller Algebra haben Knuth-Bendix 1967 substitutionsvertraegliche Wohlordnungen auf Termen benuetzt. Insbesondere fuer einstellige Operationssymbole benoetigen sie konkatenationsvertraegliche Ordnungen fuer Woerter. Eine wachsende Schar von anwendungsorientierten Experten aus u.a. Japan und England haben sich darum bemueht.
Die Leebsche Synthese
Prof. Dr. phil. Klaus Leeb, dem Inhaber des Theorielehrstuhls der Erlanger Informatik, gelang nun eine glueckliche Synthese. In einer seiner Vorlesungen hatte er automatische Gruppen (ein hochmodernes, auch als "word processing in groups" bezeichnetes Thema) behandelt. Hintergrund dazu waren die von Lyndon eingefuehrten Laengenfunktionen. Nach Lyndon war Nancy Harrison phantasievoll genug, auch reellzahlige Laengen zu verwenden. Schliesslich loeste Chiswell eine ganze Lawine von Beitraegen zu diesem Thema aus. Leeb verflocht nun die zwei Straenge von Ideen "Stellensysteme" und "symbolabhaengige reelle Laengen" zu einem neuen Tau. Diese Leebsche Synthese liefert erstmals Ordnungen, die Laengen L, Hoehen H bzw. Gewichte W und den Stellenwachstumsfaktor G unabhaengig voneinander reell bis infinitesimal (von diversen Graden) gestalten.
Als verstaendnisfoerdernde Metapher kann die allgemeine Relativitaetstheorie dienen: So wie dort erst die Massen sich ihren Raum bauen, schaffen sich hier die Symbole ihre Stellen selbst.
Ein Beispiel fuer Kundige
Fuer besonders Geduldige ein durchgerechnetes Beispiel:
Das Alphabet besteht aus den drei Elementen A, B und C. Der reelle Wachstumsfaktor (von links nach rechts) G des Stellensystems betraegt 3/2. Die reellwertigen Laengen sind LA=2, LB=1/2, LC=*2, die reellwertigen Gewichte WA=1, WB=1/3, WC=4/5.
Wir vergleichen die Woerter BBBCCBA und CAAC. Fuegt man ein Symbol rechts hinzu, so aendert sich die Laenge zu Lneu = Lalt + Laktuelles Symbol, und es aendert sich das Gewicht zu Wneu = Walt + (G^Lalt)*Waktuelles Symbol. Die Laengen der genannten Woerter stimmen dann ueberein und sind 6.828..., waehrend sich die Gewichte unterscheiden, WBBBCCBA=14.33... von WCAAC=13.75..., also betrachten wir CAAC als kleiner gegenueber BBBCCBA. Wem es beliebt, der kann auch die Gewichte durch "Hoehen" ersetzen nach der Formel Hi = Wi*logG/(G^Li-1). Dies erleichtert dann den Grenzuebergang zu G=0 (lexikographisch von links) und zu G=* (lexikographisch von rechts).
Wenn man sich die Bluete der algorithmischen Polynom-(=kommutativen)Algebra durch die Technik der Groebnerbasen ansieht (ein Werkzeug, das z.B. geometrische Probleme bei Roboterarmen loest) und beruecksichtigt, dass ihr Funktionieren von Hahns (1907) translationsinvarianten Ordnungen abhaengt, so mag man mit Recht hoffen, dass parallel zu einer Klassifikation der konkatenationsvertraeglichen Ordnungen entsprechende Reduktionssysteme fuer die nichtkommutative Algebra entstehen werden. Anwendungen warten nur darauf: Seriell-parallele Prozesse, Kommunikationsprotokolle u.a.m..
Klaus Leeb
Weitere Informationen zu diesem Thema und ueber andere Ergebnisse der Forschung im Umfeld findet der Interessierte auf Leebs Homepage. (http://www1.informatik.uni-erlangen.de/)
Kontakt: Prof. Dr. Klaus Leeb, Lehrstuhl fuer Informatik (Automatentheorie und Formale Sprachen), Martensstrasse 3, 91058 Erlangen, Tel.: 09131/85 -7924
Merkmale dieser Pressemitteilung:
Informationstechnik, Mathematik, Physik / Astronomie
überregional
Es wurden keine Arten angegeben
Deutsch
Sie können Suchbegriffe mit und, oder und / oder nicht verknüpfen, z. B. Philo nicht logie.
Verknüpfungen können Sie mit Klammern voneinander trennen, z. B. (Philo nicht logie) oder (Psycho und logie).
Zusammenhängende Worte werden als Wortgruppe gesucht, wenn Sie sie in Anführungsstriche setzen, z. B. „Bundesrepublik Deutschland“.
Die Erweiterte Suche können Sie auch nutzen, ohne Suchbegriffe einzugeben. Sie orientiert sich dann an den Kriterien, die Sie ausgewählt haben (z. B. nach dem Land oder dem Sachgebiet).
Haben Sie in einer Kategorie kein Kriterium ausgewählt, wird die gesamte Kategorie durchsucht (z.B. alle Sachgebiete oder alle Länder).
