Polynomielle Schranken für N-gewichtete Wort-Automaten
Johannes Waldmann, HTWK Leipzig.

Wir betrachten gewichtete Automaten über endlichen Wörtern.
Die Gewichte sind aus (N,plus,mal). Uns interessiert die Frage,
wann die durch den Automaten berechnete Gewichtsfunktion
durch ein Polynom in der Wortlänge beschränkt ist.

Damit verwandt ist die Frage nach der polynomiellen Mehrdeutigkeit
von klassischen Wortautomaten. Die dafür bekannten
Entscheidungsverfahren lassen sich übertragen.

Wir wenden diese Resultate an bei der Komplexitätsanalyse
von Ersetzungssystemen: das Gewicht eines Wortes beschränkt
dabei die Länge der dort beginnenden Ableitungen.

Für diese Anwendung beschreiben wir die Kompatibilität des Automaten 
mit einem gegebenen Ersetzungssystem sowie seine polynomielle Beschränktheit 
durch ein Constraint-System, dessen Lösung dann maschinell gesucht wird.

Dieses Verfahren enthält bisher benutzte Methoden 
zur Gewinnung polynomieller Ableitungsschranken 
(vgl. http://termination-portal.org/wiki/Complexity)
als Spezialfall und ist stärker als diese.

Trotzdem bleibt das folgenden Problem weiter offen: Sind die Ableitungslängen 
für { aa -> bc, bb -> ac, cc -> ab } polynomiell beschränkt?
http://rtaloop.mancoosi.univ-paris-diderot.fr/problems/105.html