Zeitliche Komplexität regulärer Sprachen

Ich frage mich, wie ich beweisen kann, dass L regulär sein muss, wenn eine Sprache L in o (nlog (n)) entscheidbar ist.

Ich sollte wahrscheinlich erwähnen, dass mit "entscheidbar" meine ich "mit einer deterministischen Einzelband-Turingmaschine entscheidbar sein".

Danke und Grüße Guillermo

Dies ist ein klassisches Ergebnis von Kobayashi. Zur Struktur der nichtdeterministischen Turing-Maschinenzeithierarchie mit einem Band , Satz 3.3 auf Seite 188. Die Idee ist, Kreuzungssequenzen zu verwenden: Sie zeigen eine Obergrenze für die Größe einer Kreuzung Verwenden Sie dann ein Argument von Hennie, Einband-Offline-Turing-Maschinenberechnungen , Satz 2 auf Seite 561, um zu dem Schluss zu kommen, dass die von der Maschine akzeptierte Sprache regulär ist.$O(1)$