Folgendes ist richtig: Es ist nicht bekannt, ob das Wortproblem in quadratischer Zeit entscheidbar ist. CYK liefert kubisch. Es gibt aber auch Möglichkeiten auf unter zu kommen! Gruß -- Gerhard Buntrock 02:59, 23. Aug 2005 (CEST)