Ich glaube, das das Wortproblem für Typ 2 Grammatiken nich in quadratischer Zeit entscheidbar ist. Schliesslich ist es, wie der Autor selbst sagt auf den CYK Algorithmus zurückzuführen und dieser hat kubische Laufzeit, damit und auch laut dem mir vorliegenden Buch ist es kubische Laufzeit.
--Gehoern 12:30, 22. Aug 2005 (CEST)