Traversierende Baumautomaten wurden bereits 1971 von Aho und Ullman untersucht. Die Berechnungsstärke dieses Modells konnte jedoch erst in den letzten Jahren besser eingeordnet werden und mit klassischen Baumautomaten-Modellen verglichen werden.

Um die Ausdrucksmächtigkeit von traversierenden Baumautomaten weiter zu erhöhen, kann man verschiedene Mechanismen zur Verwendung von Marken hinzufügen. Das Verhalten hierbei unterscheidet sich vor allem dadurch, ob man eine gelegte Marke nur von der Position der Marke aus oder von einer beliebigen Position aus wieder entfernen darf. Im ersten Fall spricht man von strikten und im zweiten Fall von schwachen Automaten.

Bojanczyk, Samuelides, Schwentick und Segoufin konnten 2006 zeigen, dass strikte und schwache traversierende Baumautomaten gleich mächtig sind. In der Diplomarbeit soll die dabei verwendete Konstruktion näher untersucht werden. Das Hauptziel ist es, die dabei auftretenden Schranken für die Größe der Automaten zu verbessern.