Eine naheliegende Verallgemeinerung von regulären (d. h. links-linearen) Wort-Grammatiken führt zur Klasse der regulären Baum-Sprachen. Man möchte das Bild abrunden durch eine dazu passende Klasse von Automaten.
Nun enthält ein Baum mehrere Teilbäume, und ein Automat kann diese nacheinander (sequentiell) oder gleichzeitig (parallel) durchlaufen. Während das parallele Modell gut untersucht ist, herrscht noch keine Einigkeit über das sequentielle Pendant. Im Vortrag berichte ich über Arbeiten zu diesem Thema von Joost Engelfriet und Hendrik Jan Hoogeboom.
Sequentielle Automaten mit endlichem Speicher, die auf Bäumen spazierengehen, können sehr wahrscheinlich nicht alle regulären Baumsprachen akzeptieren. Man gestattet deswegen diesen Automaten, im Baum Markierungen (pebbles) anzubringen.
Es ist bis heute nicht genau bekannt, wie sehr sich durch Pebbles die Rechenkraft erhöht. Die Klasse der damit akzeptierbaren Sprachen ist jedenfalls eine Teilklasse der regulären Baumsprachen, und enthält die Klasse der First-Order-definierbaren Baumsprachen. Man vermutet, daß die erstgenannte Inklusion strikt ist.