Non-negative integer basis algorithms for linear equations with integer coefficients (Q908692)

Bei der Unifikation assoziativ-kommutativer Terme stellt sich die Frage nach einem effizienten Verfahren zur Aufzählung der Lösungsbasis für eine lineare homogene Gleichung in vielen Unbekannten mit ganzzahligen Koeffizienten. Dem bloßen Ausschöpfen von Restriktionen für die Basisvektoren [\textit{G. Huet}, Inform. Processing Letters 7, 144-147 (1978; Zbl 0377.10011)] werden hier konstruktive Verfahren gegenübergestellt, die auf sukzessives Ergänzen einer Matrix hinauslaufen, deren 1. Spalte alle Koeffizienten enthält; ergänzt wird die Matrix um reduzierte Summen von je 2 Zeilen. Verf. zeigt, daß dies Prinzip terminiert, sobald eine komplette Basis erschienen ist. Aus der Trennungseigenschaft der durch die lineare Gleichung definierten Hyperebene gewinnt er dann einen eleganten Mengenalgorithmus, der dem Ref. Fragen nach seiner Optimalität als reizvoll nahelegt. Messungen ergaben durchschnittlich die halbe Laufzeit des Ausschöpfungsverfahrens; die Beispiele, in denen letzteres ``beliebig'' gegen den neuen Algorithmus abfällt, lassen dessen genauere Laufzeitanalyse sogar dringlich werden.