idw – Informationsdienst Wissenschaft

Nachrichten, Termine, Experten

Grafik: idw-Logo
Science Video Project
idw-Abo

idw-News App:

AppStore

Google Play Store



Instance:
Share on: 
03/10/1998 00:00

Uraltes Basiswerkzeug für die moderne mechanische Algebra neu 'geschärft'

Dr.rer.pol. Dipl.-Kfm. Ragnwolf Knorr Presse und Kommunikation
Friedrich-Alexander-Universität Erlangen-Nürnberg

    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


    Images

    Criteria of this press release:
    Information technology, Mathematics, Physics / astronomy
    transregional, national
    No categories were selected
    German


     

    Help

    Search / advanced search of the idw archives
    Combination of search terms

    You can combine search terms with and, or and/or not, e.g. Philo not logy.

    Brackets

    You can use brackets to separate combinations from each other, e.g. (Philo not logy) or (Psycho and logy).

    Phrases

    Coherent groups of words will be located as complete phrases if you put them into quotation marks, e.g. “Federal Republic of Germany”.

    Selection criteria

    You can also use the advanced search without entering search terms. It will then follow the criteria you have selected (e.g. country or subject area).

    If you have not selected any criteria in a given category, the entire category will be searched (e.g. all subject areas or all countries).