[2] verweist auf:
A. Gräf. Left-to-right tree pattern matching. In: Proceedings Rewriting Techniques and Applications
(RTA \'91, Como). Springer, Berlin, 1991, pp. 323-334.
Gräf selber hat diese 2 Formeln in seiner Diplomarbeit verwendet, antwortet aber leider nicht auf unsere ANfrage.
\pi ist jeweils ein "Item" in einem Patternset, in diesem Fall vom Ausgangpunkt, also die einzelnen gegebenen Muster.
|\pi| ist jeweils ihre Länge.
Das Problem ist, daß der Automat zwar wirklich nicht höher sein kann, als die Summation dieser, aber er kann auch nicht mal annähernd dies erreichen. Da frage ich mich, ob das dann wirklich der Worstcase ist, wenn mit zunehmenden Komplexität die Differenz zwischen berechnetem und tatsächlichem worst Case immer größer wird.
Schließlich ist das bei der Breite noch schlimmer, wo diese Differenz mehr als im Quadrat zu wachsen scheint.
Es ist leider so, daß der Schlimmste Fall, den ich mir vorstellen kann später nichtmal zu 5% den Wert der Rechnung erreicht.
Ich hoffte und hoffe, daß irgendjemand diese Formel schon einmal sah oder die Rechnung eines Baum-Automaten dieser Art bereits vornahm. Ich verlange aber nicht von euch, daß ihr jetzt extra neu alles herleitet
Mir scheinen Gräfs Formeln viel zu hoch gegriffen, und das ist gerade für eine worstCaseBetrachtung nicht gesund ... oder?
Danke aber für dieses Interesse, da mein Referat unbedingt fertig werden muß und niemand sonst sich diesem Problem auch nur mit einer Zeile widmete :e@sy :OD